Minimum Number of Days to Eat N Oranges: BFS with Memoization

You have n oranges. Each day you can choose one of three actions: eat 1 orange, eat n/2 oranges if n is divisible by 2, or eat 2n/3 oranges if n is divisible by 3. Return the minimum number of days to eat all of the oranges.

This is LeetCode 1553: Minimum Number of Days to Eat N Oranges, and it teaches one of the most important lessons in competitive programming: sometimes the search space is much, much smaller than it looks.

Why this problem matters

At first glance, this looks like a standard DP problem where you define dp[i] as the minimum days to eat i oranges and fill it from 0 to n. But n can be up to 2 * 10^9. You cannot allocate an array that large, let alone iterate through it. A naive bottom-up approach is completely off the table.

This problem forces you to rethink what "dynamic programming" means. Instead of iterating over all states, you learn to identify which states actually matter and only visit those. The result is a solution that runs in O(log^2 n) time on a problem that seems to require O(n). That gap between the apparent complexity and the actual complexity is the real lesson here.

The key insight

Think about what the three operations do. Eating 1 orange decreases n by 1. Eating n/2 cuts n in half. Eating 2n/3 cuts n to a third. The division operations are vastly more powerful than eating one at a time.

So the only reason you would ever eat 1 orange is to make n divisible by 2 or 3 so you can then divide. From n, you eat n % 2 oranges one at a time (0 or 1 day) to make it divisible by 2, then divide. Or you eat n % 3 oranges one at a time (0, 1, or 2 days) to make it divisible by 3, then divide. You take whichever path is cheaper.

This gives us the recurrence:

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

The 1 + accounts for the day you divide. The n % 2 or n % 3 accounts for the days you spend eating one orange to reach divisibility.

Why does this reduce the search space so dramatically? Each recursive call either halves or thirds n. Starting from n, you reach n//2 or n//3, then n//4 or n//6 or n//9, and so on. The total number of distinct values you visit is O(log^2 n), because you are combining at most O(log n) halvings with at most O(log n) thirdings. For n = 10^9, that is only a few hundred states, not a billion.

The solution

from functools import lru_cache

def min_days(n: int) -> int:
    @lru_cache(maxsize=None)
    def solve(n):
        if n <= 1:
            return n
        return 1 + min(
            n % 2 + solve(n // 2),
            n % 3 + solve(n // 3)
        )
    return solve(n)

Let's walk through each piece.

The base case handles n = 0 (return 0, no oranges to eat) and n = 1 (return 1, eat the last orange). For any larger n, we compute two options: make n divisible by 2 and divide, or make n divisible by 3 and divide. The n % 2 term is the cost of eating oranges one at a time until n becomes even. The n % 3 term is the cost until n becomes a multiple of 3. The 1 + is the day spent dividing. We take the minimum.

The @lru_cache decorator memoizes results so each unique value of n is computed only once. Since the recursion only ever calls solve(n // 2) or solve(n // 3), the set of values that get computed is small. Starting from some large n, you branch into n//2 and n//3. Each of those branches into their own halves and thirds. The total number of unique arguments is bounded by O(log^2 n).

Visual walkthrough

Let's trace through n = 10 to see how the recursion explores only a handful of states instead of all 10.

Notice that we never visited 7, 6, or any value between 5 and 10 except 9. The recursion jumped directly to the values that matter: the ones you reach by dividing. That is the power of this approach. For n = 10^9, the recursion visits roughly the same number of states as it does for n = 10, just with larger numbers.

Complexity analysis

Time is O(log^2 n). Each recursive call either halves or thirds n. The total number of distinct (n//2^a) * (1//3^b) values for all valid a and b is at most O(log_2(n) * log_3(n)), which is O(log^2 n).

Space is O(log^2 n) for the memoization cache and the recursion stack. Each cached entry stores one integer result for one subproblem.

The building blocks

1. Recursive memoization with division pruning

The core technique is recognizing that division operations collapse the search space. Instead of a linear scan from 0 to n, you let the recursion discover the tiny set of subproblems that actually matter. This pattern applies whenever a problem has operations that shrink the input by a constant factor (halving, thirding, dividing by k). You see the same idea in problems like Integer Replacement (LeetCode 397), where you halve or adjust by 1, and the actual number of states visited is logarithmic.

2. Greedy reduction to divisibility

The insight that "eating 1" is only useful for making n divisible by 2 or 3 is a greedy observation. You would never eat 1 orange four times in a row, because by then you have passed at least one multiple of 2 or 3 and missed a chance to divide. This greedy pruning is what lets you collapse the three operations into a two-branch recursion. The same reasoning appears in any problem where a cheap operation exists only to enable an expensive one.

Edge cases

Before submitting, think through these scenarios:

• n = 1: eat the one orange. Answer is 1.
• n = 2: eat half (1 day). Answer is 2. Wait, let's check: solve(2) = 1 + min(0 + solve(1), 2%3 + solve(0)) = 1 + min(1, 2+0) = 2. Yes, 2 days.
• n = 3: eat 2/3 to get 1, then eat 1. solve(3) = 1 + min(1 + solve(1), 0 + solve(1)) = 1 + min(2, 1) = 2. Answer is 2.
• Very large n (10^9): the solution handles this in microseconds because only O(log^2 n) states are visited. No array allocation, no iteration through a billion values.

From understanding to recall

The logic here is clean once you see it: always try to divide, and only eat 1 to reach divisibility. But the hard part in an interview is making that leap. You see n up to 2 * 10^9 and your first instinct is "I cannot do DP on this." The key skill is recognizing that division collapses the state space, and that the recursion will only visit O(log^2 n) values.

Spaced repetition helps you internalize that recognition. After a few rounds of writing the recurrence from scratch, the pattern becomes automatic: "large n, division operations, tiny state space, recursive memoization." You stop thinking about bottom-up tables and immediately reach for the top-down approach with pruning.

The recursive memoization with division pruning pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• Climbing Stairs - The simplest recursive-to-DP conversion, and the foundation for understanding memoization
• Coin Change - Classic DP where you minimize operations, same flavor of "pick the best option at each step"
• Number of Dice Rolls With Target Sum - Another problem where understanding which states matter dramatically simplifies the approach

CodeBricks breaks Minimum Number of Days to Eat N Oranges into its recursive memoization and greedy division building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a problem with massive n but logarithmic structure shows up in your interview, you do not hesitate. You just write it.