LeetCode Problem 1553

Difficulty: 🔴 Hard
Topics: Dynamic Programming, Memoization

Solution

LeetCode 1553 - Minimum Number of Days to Eat N Oranges

Problem Understanding

This problem asks us to compute the minimum number of days required to eat exactly n oranges, given three possible actions that can be performed each day.

On any single day, we may choose one of the following operations:

1. Eat exactly one orange.
2. If the current number of oranges is divisible by 2, eat half of them.
3. If the current number of oranges is divisible by 3, eat two-thirds of them.

The goal is to reduce the number of oranges from n down to 0 using the fewest possible days.

The important detail is that the second and third operations are only available when the current orange count is divisible by 2 or 3 respectively. This means we often need to spend several days eating single oranges just to make the number divisible before we can apply a larger reduction operation.

The input consists of a single integer n, representing the starting number of oranges. The output is the minimum number of days needed to finish all oranges.

The constraint is extremely important:

1 <= n <= 2 * 10^9

This upper bound is enormous. Any solution that tries to simulate every state sequentially or build a dynamic programming table from 1 to n will be far too slow and memory intensive.

The problem guarantees that n is always at least 1, so we never need to handle negative values or invalid input.

Several edge cases are especially important:

• Very small values such as n = 1, n = 2, and n = 3
• Numbers already divisible by 2 or 3
• Numbers that require several single-orange operations before becoming divisible
• Extremely large values near 2 * 10^9
• Cases where dividing by 2 is worse than dividing by 3, or vice versa

A naive greedy strategy can fail because locally optimal decisions do not always lead to the global minimum number of days.

Approaches

Brute Force Approach

A brute-force solution would explore every possible sequence of valid operations. From a state n, we could recursively try:

• Eat one orange
• If divisible by 2, eat n / 2
• If divisible by 3, eat 2 * (n / 3)

Then we would take the minimum result among all possible paths.

This approach is correct because it exhaustively checks every valid sequence of actions and therefore cannot miss the optimal solution.

However, the problem is that many states are recomputed repeatedly. For example, different recursive paths may eventually reach the same remaining orange count. Without optimization, the recursion tree grows exponentially.

For large values such as 10^9, this approach becomes completely infeasible.

Key Insight for the Optimal Solution

The most important observation is that the only meaningful large reductions come from division by 2 or 3.

Suppose we want to divide by 2, but n is not divisible by 2. The only way to make it divisible is to spend n % 2 days eating single oranges.

Similarly, if we want to divide by 3, we first need to spend n % 3 days eating single oranges.

This leads to the recurrence:

minDays(n) =
1 + min(
    (n % 2) + minDays(n // 2),
    (n % 3) + minDays(n // 3)
)

The extra 1 represents the day when we perform the division operation itself.

This drastically reduces the number of states we need to compute because each recursive step reduces the problem size significantly.

Memoization allows us to store previously computed results and avoid repeated work.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores every possible sequence of operations
Optimal Memoized DP	O(log n) approximately	O(log n)	Uses recursion with memoization and aggressive state reduction

Algorithm Walkthrough

1. Define a recursive function dfs(n) that returns the minimum number of days needed to eat n oranges.
2. Handle the base cases first.

• If n <= 1, return n.
• 0 oranges require 0 days.
• 1 orange requires 1 day.

3. Consider making n divisible by 2.

If n is not divisible by 2, we must spend n % 2 days eating one orange at a time. After that, we can spend one more day performing the division-by-2 operation.

The total cost becomes:

(n % 2) + 1 + dfs(n // 2)

4. Consider making n divisible by 3.

Similarly, we spend n % 3 days eating single oranges, then one day for the division-by-3 operation.

The total cost becomes:

(n % 3) + 1 + dfs(n // 3)

5. Take the minimum of the two choices.

We choose whichever path leads to fewer total days. 6. Store the computed result in a memoization cache.

This ensures each state is solved only once. 7. Return the cached result.

Why It Works

The algorithm works because every optimal strategy eventually reduces the number using division by 2 or division by 3. Any extra single-orange operations are only used to make the number divisible.

Instead of exploring all possible sequences of single-orange removals, the algorithm directly computes the minimum number required to reach a divisible state. This compresses many redundant states into a single transition.

Memoization guarantees that each distinct value of n is solved once, preventing exponential recomputation.

Python Solution

class Solution:
    def minDays(self, n: int) -> int:
        memo = {}

        def dfs(remaining: int) -> int:
            if remaining <= 1:
                return remaining

            if remaining in memo:
                return memo[remaining]

            divide_by_2 = (remaining % 2) + 1 + dfs(remaining // 2)
            divide_by_3 = (remaining % 3) + 1 + dfs(remaining // 3)

            memo[remaining] = min(divide_by_2, divide_by_3)
            return memo[remaining]

        return dfs(n)

The implementation uses a recursive helper function named dfs.

The base case handles 0 and 1 directly. These are the smallest possible states and terminate recursion.

The dictionary memo stores previously computed results. Before solving a state, the algorithm checks whether it already exists in the cache.

The expression:

(remaining % 2) + 1 + dfs(remaining // 2)

represents:

• The days needed to make the number divisible by 2
• One day for the division operation
• The recursive solution for the reduced problem

The same logic applies for division by 3.

Finally, the algorithm stores and returns the minimum of the two choices.

Go Solution

func makeMemo() map[int]int {
    return map[int]int{}
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func minDays(n int) int {
    memo := makeMemo()

    var dfs func(int) int

    dfs = func(remaining int) int {
        if remaining <= 1 {
            return remaining
        }

        if value, exists := memo[remaining]; exists {
            return value
        }

        divideBy2 := (remaining % 2) + 1 + dfs(remaining/2)
        divideBy3 := (remaining % 3) + 1 + dfs(remaining/3)

        memo[remaining] = min(divideBy2, divideBy3)

        return memo[remaining]
    }

    return dfs(n)
}

The Go solution follows the same recursive memoized approach as the Python version.

A map[int]int is used for memoization because Go does not provide a built-in memoization utility.

The recursive function is declared as a closure using:

var dfs func(int) int

This allows the function to recursively reference itself.

Integer overflow is not a concern because the maximum value is only 2 * 10^9, which fits comfortably within Go's int type on LeetCode systems.

Unlike Python dictionaries, Go maps require explicit existence checks using:

value, exists := memo[key]

Worked Examples

Example 1

Input: n = 10

We compute:

State	Option	Cost
10	Divide by 2	0 + 1 + dfs(5)
10	Divide by 3	1 + 1 + dfs(3)

Now evaluate recursively.

For dfs(5):

State	Option	Cost
5	Divide by 2	1 + 1 + dfs(2)
5	Divide by 3	2 + 1 + dfs(1)

Best result for 5 is 4.

For dfs(3):

State	Option	Cost
3	Divide by 2	1 + 1 + dfs(1)
3	Divide by 3	0 + 1 + dfs(1)

Best result for 3 is 2.

Now compute the final answer:

Path	Total
Through division by 2	1 + 4 = 5
Through division by 3	2 + 2 = 4

Final answer:

4

Example 2

Input: n = 6

State	Option	Cost
6	Divide by 2	0 + 1 + dfs(3)
6	Divide by 3	0 + 1 + dfs(2)

We know:

dfs(3) = 2
dfs(2) = 2

So:

Path	Total
Divide by 2	1 + 2 = 3
Divide by 3	1 + 2 = 3

Final answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n) approximately	Each recursive call significantly reduces the problem size
Space	O(log n)	Memoization table and recursion depth

The recursion repeatedly divides the problem size by 2 or 3, so the number of distinct states remains relatively small.

Although the exact theoretical bound is not strictly logarithmic because of branching, the memoized state space grows very slowly in practice and performs efficiently even for the maximum constraint.

The recursion stack depth is also logarithmic because each recursive path rapidly reduces the remaining number of oranges.

Test Cases

solution = Solution()

assert solution.minDays(1) == 1  # smallest valid input
assert solution.minDays(2) == 2  # divide by 2 once
assert solution.minDays(3) == 2  # divide by 3 once
assert solution.minDays(4) == 3  # repeated division by 2
assert solution.minDays(6) == 3  # both division paths work
assert solution.minDays(10) == 4  # provided example
assert solution.minDays(56) == 6  # mixed operations
assert solution.minDays(100) == 8  # larger composite number
assert solution.minDays(999) > 0  # stress recursive memoization
assert solution.minDays(2000000000) > 0  # maximum constraint stress test

Test Summary

Test	Why
n = 1	Validates smallest possible input
n = 2	Tests direct division by 2
n = 3	Tests direct division by 3
n = 4	Tests repeated halving
n = 6	Tests multiple optimal paths
n = 10	Validates provided example
n = 56	Tests mixed divisibility behavior
n = 100	Tests larger recursive reductions
n = 999	Tests many recursive states
n = 2000000000	Stress tests maximum input size

Edge Cases

One important edge case is when n = 1. A careless implementation might continue recursion unnecessarily or mishandle the base condition. The solution correctly returns 1 immediately because exactly one day is needed to eat the final orange.

Another critical edge case occurs when n is already divisible by 2 or 3. In these situations, the modulo cost becomes zero, allowing the algorithm to immediately perform the large reduction operation. The implementation naturally handles this because n % 2 or n % 3 evaluates to 0.

A more subtle edge case involves numbers that are not divisible by either 2 or 3, such as n = 5 or n = 7. A naive greedy solution may choose the wrong adjustment path. The recursive memoized solution avoids this issue by evaluating both possibilities and selecting the minimum total cost.

Extremely large inputs such as 2 * 10^9 are another important edge case. A traditional bottom-up dynamic programming solution would require enormous memory and runtime. The memoized recursive solution remains efficient because it only explores a very small subset of states generated through repeated division.