Watch 10 video solutions for Minimum Number of Days to Eat N Oranges, a hard level problem involving Dynamic Programming, Memoization. This walkthrough by NeetCode has 15,700 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are n oranges in the kitchen and you decided to eat some of these oranges every day as follows:
n is divisible by 2 then you can eat n / 2 oranges.n is divisible by 3 then you can eat 2 * (n / 3) oranges.You can only choose one of the actions per day.
Given the integer n, return the minimum number of days to eat n oranges.
Example 1:
Input: n = 10 Output: 4 Explanation: You have 10 oranges. Day 1: Eat 1 orange, 10 - 1 = 9. Day 2: Eat 6 oranges, 9 - 2*(9/3) = 9 - 6 = 3. (Since 9 is divisible by 3) Day 3: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. Day 4: Eat the last orange 1 - 1 = 0. You need at least 4 days to eat the 10 oranges.
Example 2:
Input: n = 6 Output: 3 Explanation: You have 6 oranges. Day 1: Eat 3 oranges, 6 - 6/2 = 6 - 3 = 3. (Since 6 is divisible by 2). Day 2: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. (Since 3 is divisible by 3) Day 3: Eat the last orange 1 - 1 = 0. You need at least 3 days to eat the 6 oranges.
Constraints:
1 <= n <= 2 * 109Problem Overview: You start with n oranges. Each day you can eat 1 orange, eat n/2 oranges if n is divisible by 2, or eat 2n/3 oranges if n is divisible by 3. The goal is to reach 0 oranges in the minimum number of days. Brute simulation quickly becomes impossible because n can be very large, so the solution must aggressively reuse subproblem results.
Approach 1: Recursive with Memoization (O(log n) time, O(log n) space)
This approach models the problem as a recurrence and stores intermediate results using memoization. For any value n, you have two meaningful strategies: make it divisible by 2 or make it divisible by 3. Instead of repeatedly subtracting 1, compute the adjustment directly using n % 2 or n % 3. For example, reaching a divisible-by-2 state costs n % 2 single-orange days, then one more day to eat n/2. The recurrence becomes 1 + min(n % 2 + f(n/2), n % 3 + f(n/3)). A hash map stores results of f(n) so repeated states are computed once. Because each step drastically reduces n by dividing it, the number of unique states grows roughly logarithmically.
Approach 2: Dynamic Programming (O(n) time, O(n) space)
A straightforward dynamic programming formulation builds answers from 1 to n. Let dp[i] represent the minimum days to finish i oranges. From each state you consider eating one orange (dp[i-1] + 1), eating half if i is divisible by 2 (dp[i/2] + 1), or eating two-thirds if divisible by 3 (dp[i/3] + 1). Iteratively fill the array while taking the minimum among valid transitions. This bottom-up strategy is easy to reason about and mirrors the recurrence, but it requires allocating a DP array of size n. For large values of n (up to billions), the memory and runtime become impractical.
Recommended for interviews: The recursive memoization approach is what interviewers expect. It shows you recognize the divide-and-conquer structure and avoid linear simulation by jumping directly to divisible states. Writing the recurrence with n % 2 and n % 3 demonstrates strong optimization instincts. Discussing the bottom-up dynamic programming formulation is still useful because it proves you understand the state transition before applying memoization to reduce the search space.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(log n) | O(log n) | Best general solution when n can be extremely large. Uses division jumps and caching. |
| Bottom-Up Dynamic Programming | O(n) | O(n) | Good for understanding transitions or when n is small enough to allocate a DP table. |