Minimum Number of Days to Eat N Oranges

How it works

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.

Steps

1. Initialize a queue with n and a visited set.
2. 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.
3. Continue until reaching 0.

Complexity

• Time complexity: O(log n)
• Space complexity: O(log n)

Things to watch for

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.

from collections import deque

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

class Solution {
public:
    int minDays(int n) {
        queue<int> q;
        unordered_set<int> visit;
        q.push(n);
        int res = 0;

        while (!q.empty()) {
            res++;
            for (int i = q.size(); i > 0; i--) {
                int node = q.front(); q.pop();
                int nei = node - 1;
                if (nei == 0) return res;
                if (visit.find(nei) == visit.end()) {
                    visit.insert(nei);
                    q.push(nei);
                }
                for (int d = 2; d <= 3; d++) {
                    if (node % d == 0) {
                        nei = node / d;
                        if (nei == 0) return res;
                        if (visit.find(nei) == visit.end()) {
                            visit.insert(nei);
                            q.push(nei);
                        }
                    }
                }
            }
        }
        return res;
    }
};