Minimum Number of Days to Eat N Oranges - Video Solutions

Problem 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.