1553. Minimum Number of Days to Eat N Oranges - Explanation

1. Dynamic Programming (Top-Down)

Intuition

At each step, we can eat one orange, half the oranges (if divisible by 2), or two-thirds of the oranges (if divisible by 3). A naive recursion explores all three options at each state and picks the minimum.

The challenge is that n can be very large, but memoization helps by caching results for previously computed values. However, this approach still explores too many states because eating one orange at a time creates many intermediate values.

Algorithm

Use a hash map to memoize results for each value of n.
Base case: if n is 0, return 0 (no days needed).
For each state, compute the minimum of:
- Eating one orange and solving for n - 1
- If divisible by 2, eating half and solving for n / 2
- If divisible by 3, eating two-thirds and solving for n / 3
Store and return the minimum result plus one day.

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

        def dfs(n):
            if n == 0:
                return 0
            if n in dp:
                return dp[n]

            res = 1 + dfs(n - 1)
            if n % 3 == 0:
                res = min(res, 1 + dfs(n // 3))
            if n % 2 == 0:
                res = min(res, 1 + dfs(n // 2))

            dp[n] = res
            return res

        return dfs(n)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Greedy + Dynamic Programming (Top-Down)

Intuition

The key optimization is recognizing that we should always try to divide rather than subtract one repeatedly. Instead of exploring n - 1 recursively (which creates exponentially many states), we can directly compute how many subtractions are needed to reach a divisible number.

To reach a number divisible by 2, we need n % 2 subtractions. To reach a number divisible by 3, we need n % 3 subtractions. By adding these remainder costs upfront, we only need to recurse on n / 2 and n / 3, drastically reducing the state space to O(log n).

Algorithm

Use a hash map with base cases: 0 oranges takes 0 days, 1 orange takes 1 day.
For each state n:
- Compute cost to divide by 2: (n % 2) remainder days + 1 division day + solve for n / 2
- Compute cost to divide by 3: (n % 3) remainder days + 1 division day + solve for n / 3
- Take the minimum of both options.
Memoize and return the result.

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

        def dfs(n):
            if n in dp:
                return dp[n]

            res = 1 + (n % 2) + dfs(n // 2)
            res = min(res, 1 + (n % 3) + dfs(n // 3))
            dp[n] = res
            return res

        return dfs(n)

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(\log n)$

3. Breadth First Search

Intuition

BFS naturally finds the shortest path in an unweighted graph. Here, each state (number of oranges) is a node, and each valid operation is an edge. Since all edges have equal cost (one day), BFS will find the minimum days when we first reach 0.

We use a visited set to avoid reprocessing the same orange count. From each state, we explore eating one orange, and optionally dividing by 2 or 3 if applicable.

Algorithm

Initialize a queue with n and a visited set.
Process level by level (each level represents one day):
- For each current orange count, try all three operations.
- If any operation results in 0, return the current day count.
- Add unvisited new states to the queue.
Continue until reaching 0.

class Solution:
    def minDays(self, n: int) -> int:
        q = deque([n])
        visit = set()
        res = 0

        while q:
            res += 1
            for _ in range(len(q)):
                node = q.popleft()
                nei = node - 1
                if nei == 0:
                    return res
                if nei not in visit:
                    visit.add(nei)
                    q.append(nei)
                for d in range(2, 4):
                    if node % d == 0:
                        nei = node // d
                        if nei == 0:
                            return res
                        if nei not in visit:
                            visit.add(nei)
                            q.append(nei)
        return res

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(\log n)$

Common Pitfalls

Recursing on n-1 Directly Causes TLE

The naive approach of recursively calling dfs(n-1) for the "eat one orange" option explores O(n) states, causing Time Limit Exceeded for large inputs. The key optimization is to never recurse on n-1 directly. Instead, compute the cost to reach the nearest divisible number: (n % 2) + 1 + dfs(n // 2) or (n % 3) + 1 + dfs(n // 3). This reduces the state space from O(n) to O(log n).

Missing Base Cases in Memoization

The optimized solution requires explicit base cases for n = 0 and n = 1 before computing the recursive formula. Forgetting dp[1] = 1 will cause infinite recursion or incorrect results since the formula 1 + (n % 2) + dfs(n // 2) does not naturally terminate at 1. Always initialize the memoization cache with {0: 0, 1: 1}.

Integer Division Confusion Across Languages

In the optimized recurrence, you compute dfs(n // 2) and dfs(n // 3). Be careful with integer division semantics. In Python, // performs floor division. In JavaScript, you need Math.floor(n / 2). Using regular division / in languages like JavaScript or Python 2 will produce floating-point results, causing cache misses and incorrect behavior.

Forgetting That All Three Options Must Be Considered

Even in the optimized solution, you must consider both paths: reducing to a multiple of 2 and reducing to a multiple of 3. Some solutions incorrectly assume one division is always better. For example, with n = 7, going via 6 (divide by 3) takes 3 days, but going via 6 then 3 then 1 needs careful comparison. Always take the minimum of both division paths.