GreedyProblem 13 of 35
Check if it is possible to survive on Island
Problem Statement
You are stuck on an island where you need to survive for n days. You can buy food only on Sundays (every 7th day starting from day 1). Each day you need exactly 1 unit of food, and the shop sells maximum m units per visit. Food costs p per unit. Additionally, you can store at most s units of food at any time.
Determine if survival is possible, and if yes, find the minimum cost to survive all n days.
Constraints:
- 1 ≤ n ≤ 365
- 1 ≤ m ≤ 100
- 1 ≤ s ≤ 1000
- 1 ≤ p ≤ 100
Example:
- Input:
n = 10,s = 16,m = 2,p = 10 - Output:
Not possible - Explanation: Can only buy 2 units per Sunday, but need 7 units for a week.
Example 2:
- Input:
n = 15,s = 10,m = 8,p = 5 - Output:
Possible, cost = 75
Approach 1: Day-by-Day Simulation (Brute Force)
Intuition
Simulate each day: on Sundays, buy as much food as possible (within shop limit and storage limit). Check if you have food each day.
Algorithm
- Start with 0 food
- For each day 1 to n:
- If Sunday (day % 7 == 1 or day == 1), buy food
- Consume 1 unit
- If food < 0, survival not possible
- Calculate total cost
java
public class SurvivalProblem {
public int[] canSurviveBrute(int n, int s, int m, int p) {
int food = 0;
int totalCost = 0;
for (int day = 1; day <= n; day++) {
// Check if it's a buying day (Sunday)
if (day % 7 == 1) {
int canBuy = Math.min(m, s - food);
food += canBuy;
totalCost += canBuy * p;
}
food--;
if (food < 0) {
return new int[]{0, -1}; // Not possible
}
}
return new int[]{1, totalCost}; // Possible
}
}Complexity Analysis
- Time Complexity: O(n) - Simulate each day
- Space Complexity: O(1) - Only tracking variables
Approach 2: Mathematical (Optimal)
Intuition
Calculate mathematically whether survival is possible and the minimum cost based on:
- Number of Sundays available
- Total food needed
- Maximum food that can be bought
Algorithm
- If
m >= 7: Can always survive if storage is sufficient - Calculate number of Sundays in n days
- Calculate if total buyable food >= total needed food
- Minimum cost = n * p (need exactly n units to survive)
java
public class SurvivalOptimal {
public int[] canSurvive(int n, int s, int m, int p) {
int numSundays = (n + 6) / 7;
int food = 0;
for (int sundayNum = 1; sundayNum <= numSundays; sundayNum++) {
int sundayDay = (sundayNum - 1) * 7 + 1;
// Buy food
int canBuy = Math.min(m, s - food);
food += canBuy;
// Days until next Sunday or end
int daysUntilNext;
if (sundayNum < numSundays) {
daysUntilNext = 7;
} else {
daysUntilNext = n - sundayDay + 1;
}
// Consume
food -= daysUntilNext;
if (food < 0) {
return new int[]{0, -1}; // Not possible
}
}
return new int[]{1, n * p}; // Possible
}
public static void main(String[] args) {
SurvivalOptimal so = new SurvivalOptimal();
int[][] tests = {
{10, 16, 2, 10},
{15, 10, 8, 5},
{7, 10, 7, 5},
};
for (int[] test : tests) {
int[] result = so.canSurvive(test[0], test[1], test[2], test[3]);
String status = result[0] == 1 ?
"Possible, cost = " + result[1] : "Not possible";
System.out.printf("n=%d, s=%d, m=%d, p=%d: %s%n",
test[0], test[1], test[2], test[3], status);
}
}
}Dry Run Example
n = 10, s = 16, m = 2, p = 10
Number of Sundays: ceil(10/7) = 2 (Day 1 and Day 8)
Week 1 (Sunday Day 1):
Food before: 0
Buy: min(2, 16-0) = 2 units
Food after buying: 2
Days to survive: 7 (until Day 8)
Food after consumption: 2 - 7 = -5
FAILED! Not enough food for week 1.
Answer: Not possible
---
n = 15, s = 10, m = 8, p = 5
Number of Sundays: ceil(15/7) = 3 (Day 1, 8, 15)
Week 1 (Sunday Day 1):
Food before: 0
Buy: min(8, 10-0) = 8 units
Food after buying: 8
Days to survive: 7 (until Day 8)
Food after consumption: 8 - 7 = 1
Week 2 (Sunday Day 8):
Food before: 1
Buy: min(8, 10-1) = 8 units
Food after buying: 9
Days to survive: 7 (until Day 15)
Food after consumption: 9 - 7 = 2
Week 3 (Sunday Day 15):
Food before: 2
Buy: min(8, 10-2) = 8 units (but only need 1)
Actually: only need to survive 1 day
Days to survive: 15 - 15 + 1 = 1
Food after consumption: 2 + bought - 1 = enough!
SURVIVED!
Minimum cost = 15 * 5 = 75
(We actually bought more than needed but minimum requirement is 15 units)
Complexity Analysis
- Time Complexity: O(n/7) = O(n) for simulation, O(1) for direct formula
- Space Complexity: O(1)
Key Takeaways
- Weekly Cycles: Problem has weekly structure (buy on Sundays)
- Critical Check: Can we survive from one Sunday to the next?
- m >= 7 Rule: If we can buy 7+ units, weekly survival is guaranteed
- Storage Constraint: Must consider storage limits when carrying over
- Minimum Cost: Always n * p (need exactly n units)
- Edge Cases: First week, last partial week
- Greedy Buying: Always buy maximum allowed each Sunday