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.
This approach uses recursion with memoization to calculate the minimum days needed to eat all oranges. At each step, we decide whether to eat one orange or reduce the count via division if divisible, storing the results of each calculation to avoid redundant computations. This ensures that we do not re-solve subproblems and optimize our approach.
This C solution uses dynamic programming with memoization. We use a helper function that solves the problem recursively and memoizes the results. For each number of oranges, we compute the minimal days required by either eating one, or using one of the allowed division operations if they are possible.
Time Complexity: O(log(n)), Space Complexity: O(n) due to stored results in memo array.
The dynamic programming approach involves bottom-up computation for minimum days starting from 1 orange to n oranges. An array stores the minimum number of days required to eat i oranges, iteratively filling this table until we reach n. Each step looks at eating one orange or using divisibility options to reduce the count.
This solution in C uses a dynamic programming approach with a dp array of size n+1, which keeps track at each index of the minimum number of days needed to eat up to that many oranges. The solution sequentially calculates this for all oranges from 1 to n, considering all possible operations allowed per day.
Time Complexity: O(n), Space Complexity: O(n) due to the dp array usage.
According to the problem description, for each n, we can choose one of three ways:
n by 1;n can be divided by 2, divide the value of n by 2;n can be divided by 3, divide the value of n by 3.Therefore, the problem is equivalent to finding the minimum number of days to reduce n to 0 through the above three ways.
We design a function dfs(n), which represents the minimum number of days to reduce n to 0. The execution process of the function dfs(n) is as follows:
n < 2, return n;n to a multiple of 2 by n bmod 2 operations of 1, and then perform operation 2 to reduce n to n/2; we can also first reduce n to a multiple of 3 by n bmod 3 operations of 1, and then perform operation 3 to reduce n to n/3. We choose the minimum of the above two ways, that is, 1 + min(n bmod 2 + dfs(n/2), n bmod 3 + dfs(n/3)).To avoid repeated calculations, we use the method of memoization search and store the calculated values of dfs(n) in a hash table.
The time complexity is O(log^2 n), and the space complexity is O(log^2 n).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Recursive with Memoization | Time Complexity: O(log(n)), Space Complexity: O(n) due to stored results in memo array. |
| Dynamic Programming | Time Complexity: O(n), Space Complexity: O(n) due to the dp array usage. |
| Memoization Search | — |
| 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. |
Minimum Number of Days to Eat N Oranges - Dynamic Programming - Leetcode 1553 - Python • NeetCode • 15,700 views views
Watch 9 more video solutions →Practice Minimum Number of Days to Eat N Oranges with our built-in code editor and test cases.
Practice on FleetCode