Log inSign up
easyGeeksforGeeksNot Started

Survival on Island

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on GeeksforGeeks
Lesson

Problem Statement

You want to buy food to survive for S days on an island. You can buy a maximum of N units of food from the shop on any single day.

To survive, you need to consume exactly M units of food each day.

The food shop is open on all days of the week except Sundays (i.e., closed on days 7, 14, 21, ...).

Find the minimum number of days on which you need to buy food to survive the entire S days. If it is impossible to survive, return -1.

Example 1 · Example 1: Survivable Case:

Input: S = 10, N = 16, M = 2
Output: 2
Explanation: Total food needed = 10 * 2 = 20 units.\nDay 1: buy 16 units.\nDay 2: buy 16 units.\nTotal 32 units bought in 2 days, which covers all 20 units needed over 10 days. Min days = 2.

Example 2 · Example 2: Sunday Starvation:

Input: S = 10, N = 2, M = 2
Output: -1
Explanation: To survive 7 days, you need 14 units of food. But in 6 open days you can only buy 6 * 2 = 12 units. You will starve on the 7th day (Sunday).

Constraints:

  • 1 <= S, N, M <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Identify weekly bottlenecks and prove the 6*N >= 7*M constraint.
  • Apply integer ceiling division correctly: (total + unit - 1) / unit.
  • Implement the O(1) solution across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Rate of production vs rate of consumption problem.
  • Cyclic unavailability (weekends / periodic closures).
  • Minimum transactions to reach target total.

Algorithmic Decision Tree:

  • Immediate failure: M > N.
  • Weekly failure: S >= 7 && 6 * N < 7 * M.
  • Total failure: (S - S/7) * N < S * M.
  • Optimal days: ceil(S * M / N).

Connected Patterns:

Gas StationLemonade ChangeMinimum Number of Coins

1. Day-by-Day Simulation

Intuition

Simulate each day chronologically from 1 to S. Keep food in hand, buying up to N whenever current food is insufficient.

Algorithm

  1. Step 1: If M > N or (S >= 7 and 6 * N < 7 * M), return -1.
  2. Step 2: Initialize foodInHand = 0, buyDays = 0.
  3. Step 3: For day 1 to S: if foodInHand < M: if day % 7 == 0 return -1 (closed!); else buyDays++, foodInHand += N.
  4. Step 4: Consume M: foodInHand -= M.
  5. Step 5: Return buyDays.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 int minimumDays(int S, int N, int M) {
8 if (M > N || (S >= 7 && 6 * N < 7 * M)) return -1;
9
10 int foodInHand = 0;
11 int buyDays = 0;
12
13 for (int day = 1; day <= S; ++day) {
14 if (foodInHand < M) {
15 if (day % 7 == 0) return -1; // Sunday: closed
16 buyDays++;
17 foodInHand += N;
18 }
19 foodInHand -= M;
20 }
21
22 return buyDays;
23 }
24};
25
26int main() {
27 Solution sol;
28 cout << "S=10, N=16, M=2: " << sol.minimumDays(10, 16, 2) << endl;
29 cout << "S=10, N=2, M=2: " << sol.minimumDays(10, 2, 2) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(S)
  • Space complexity: O(1)

2. Binary Search on Purchase Days

Intuition

Binary search on the minimum number of days needed to buy food within range [1, S - S/7].

Algorithm

  1. Step 1: Check feasibility: M <= N and (S < 7 or 6 * N >= 7 * M). If not, return -1.
  2. Step 2: Low = 1, High = S - S / 7, ans = -1.
  3. Step 3: Mid = (Low + High) / 2.
  4. Step 4: If Mid * N >= S * M, record ans = Mid and search left (High = Mid - 1).
  5. Step 5: Else search right (Low = Mid + 1).
  6. Step 6: Return ans.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 int minimumDays(int S, int N, int M) {
8 if (M > N || (S >= 7 && 6 * N < 7 * M)) return -1;
9
10 int totalBuyDays = S - S / 7;
11 if (totalBuyDays * N < S * M) return -1;
12
13 int low = 1, high = totalBuyDays, ans = -1;
14 while (low <= high) {
15 int mid = low + (high - low) / 2;
16 if (mid * N >= S * M) {
17 ans = mid;
18 high = mid - 1;
19 } else {
20 low = mid + 1;
21 }
22 }
23 return ans;
24 }
25};
26
27int main() {
28 Solution sol;
29 cout << "S=10, N=16, M=2 (BS): " << sol.minimumDays(10, 16, 2) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(log S)
  • Space complexity: O(1)

3. Direct Mathematical Greedy Formula

Intuition

Verify Sunday starvation and total food constraints in O(1). Compute ceiling of total food needed divided by single-day purchase capacity.

Algorithm

  1. Step 1: If M > N, return -1 (cannot afford 1 day's food).
  2. Step 2: If S >= 7 and 6 * N < 7 * M, return -1 (cannot survive the first Sunday).
  3. Step 3: Total food required is S * M.
  4. Step 4: Available buying days is S - S / 7.
  5. Step 5: If available buying days * N < S * M, return -1.
  6. Step 6: Return ceil((S * M) / N) = (S * M + N - 1) / N.

Interactive Trace for Survival on Island

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Check Sunday feasibility: 6 N = 6 16 = 96 >= 7 M = 14
Visual state
Values and pointers at this exact step
pointers
S
96 units
14 units
0
↑ weekCheck
1
Check / comparison
96 >= 14 (Can survive past day 7)
Decision / next transition
Weekly constraint satisfied.
Why this step matters

Step 1: Check Sunday feasibility: 6 * N = 6 * 16 = 96 >= 7 * M = 14. Survivable through Sunday.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 int minimumDays(int S, int N, int M) {
8 if (M > N) return -1;
9 if (S >= 7 && 6 * N < 7 * M) return -1;
10
11 int totalBuyDays = S - S / 7;
12 int totalFoodNeeded = S * M;
13
14 if (totalBuyDays * N < totalFoodNeeded) return -1;
15
16 return (totalFoodNeeded + N - 1) / N;
17 }
18};
19
20int main() {
21 Solution sol;
22 cout << "S=10, N=16, M=2: " << sol.minimumDays(10, 16, 2) << endl;
23 cout << "S=10, N=2, M=2: " << sol.minimumDays(10, 2, 2) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(1)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Day-by-Day SimulationO(S)O(1)Simulate each day from day 1 to S. Track food in hand. If current food is insufficient for the day and the shop is open, buy up to N units. Count purchase days.Daily iteration.
2.Better — Binary Search on DaysO(log S)O(1)Binary search on the number of buying days D in range [1, S - S/7]. Test if D * N >= S * M and weekly survival constraints hold.Binary search steps.
3.Optimal — Direct Mathematical GreedyOptimalO(1)O(1)Verify feasibility bounds in O(1). Compute ceiling of total food required divided by max food per day: (S * M + N - 1) / N.Arithmetic operations.
Back to DSA Sheet