Check if it is possible to survive on Island

The problem, simply

You are on an island for S days. Today is Monday. There is one shop. It is open every day except Sunday, and on each visit it sells you at most N units of food. You must eat M units every day, and you can store as much food as you like.

Give back the smallest number of days you need to go shopping to survive all S days, or -1 if you cannot survive. You may shop and then eat on the same day.

A story to remember it

Picture it

Examples

Way 1: the simple way

Live through every day.

1. Keep food in the pantry and bought so far.
2. On each day that is not a Sunday, if you have not yet bought S * M in total, buy N and count one shopping day.
3. Eat M. If food drops below 0, return -1.
4. After the last day, return the count.

Buying as early as possible is never worse, because stored food does not spoil.

class Solution {
    public int minimumDays(int S, int N, int M) {
        long need = (long) S * M;
        long food = 0, bought = 0;
        int days = 0;
        for (int d = 1; d <= S; d++) {
            boolean sunday = d % 7 == 0;          // day 1 is Monday
            if (!sunday && bought < need) {
                food += N;
                bought += N;
                days++;
            }
            food -= M;                            // eat
            if (food < 0) return -1;
        }
        return days;
    }
}

How long it takes: one step per day, O(S). Extra room: a few numbers, O(1).

Way 2: the clever way

Three small checks replace the whole simulation.

1. If M > N, you starve on day 1. Return -1.
2. If you stay at least 7 days, the first Sunday is the danger. By then you can have bought at most 6 * N and you have eaten 7 * M. If 6 * N < 7 * M, return -1. If it passes, every later week works the same way, so you never starve.
3. Otherwise you need S * M units, and each visit gives at most N. The answer is S * M / N rounded up.

class Solution {
    public int minimumDays(int S, int N, int M) {
        if (M > N) return -1;                              // starve on day 1
        if (S >= 7 && 6L * N < 7L * M) return -1;          // starve on the first Sunday
        long need = (long) S * M;
        return (int) ((need + N - 1) / N);                 // visits, rounded up
    }
}

How long it takes: a few multiplications, O(1). Extra room: O(1).

Watch out for

• Day 1 is Monday, so Sundays are days 7, 14, 21, and so on.
• S * M can be large. Use long before dividing.
• Round up: (need + N - 1) / N, not need / N.
• If you stay fewer than 7 days, there is no Sunday, so skip the Sunday check.

What interviewers ask next

• Why does passing the first Sunday mean every later Sunday is fine? Each full week you can buy 6 * N and eat 7 * M. If one week works, the food left over only grows, week after week.
• Why is shopping early always best? Food keeps, so having it sooner never hurts. That is why the fewest visits is the rounded up division.
• What if the pantry can hold at most C units? Then you cannot stock up for Sunday freely. Simulate, buying min(N, C - food) each open day, and the answer can change.
• What if today is not Monday? Count the open days before the first Sunday and check that open * N >= (open + 1) * M, then use the same weekly check.

Remember this

Grown-up words: the pantry is a running balance, shopping early is a greedy choice, and the weekly check is the invariant that makes the closed form answer safe.