Skip to main content
Talentd

Minimum Number of Days to Eat N Oranges - Solution & Explanation

HardDynamic ProgrammingMemoization20 min readAsked at: Google
Practice this problem

Problem Statement

There are n oranges in the kitchen and you decided to eat some of these oranges every day as follows:

  • Eat one orange.
  • If the number of remaining oranges n is divisible by 2 then you can eat n / 2 oranges.
  • If the number of remaining oranges n is divisible by 3 then you can eat 2 * (n / 3) oranges.

You can only choose one of the actions per day.

Given the integer n, return the minimum number of days to eat n oranges.

 

Example 1:

Input: n = 10
Output: 4
Explanation: You have 10 oranges.
Day 1: Eat 1 orange,  10 - 1 = 9.  
Day 2: Eat 6 oranges, 9 - 2*(9/3) = 9 - 6 = 3. (Since 9 is divisible by 3)
Day 3: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. 
Day 4: Eat the last orange  1 - 1  = 0.
You need at least 4 days to eat the 10 oranges.

Example 2:

Input: n = 6
Output: 3
Explanation: You have 6 oranges.
Day 1: Eat 3 oranges, 6 - 6/2 = 6 - 3 = 3. (Since 6 is divisible by 2).
Day 2: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. (Since 3 is divisible by 3)
Day 3: Eat the last orange  1 - 1  = 0.
You need at least 3 days to eat the 6 oranges.

 

Constraints:

  • 1 <= n <= 2 * 109

Approach Overview

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.

Approach 1: Recursive with Memoization

This approach uses recursion with memoization to calculate the minimum days needed to eat all oranges. At each step, we decide whether to eat one orange or reduce the count via division if divisible, storing the results of each calculation to avoid redundant computations. This ensures that we do not re-solve subproblems and optimize our approach.

This C solution uses dynamic programming with memoization. We use a helper function that solves the problem recursively and memoizes the results. For each number of oranges, we compute the minimal days required by either eating one, or using one of the allowed division operations if they are possible.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log(n)), Space Complexity: O(n) due to stored results in memo array.

Try this approach in the editor →

Approach 2: Dynamic Programming

The dynamic programming approach involves bottom-up computation for minimum days starting from 1 orange to n oranges. An array stores the minimum number of days required to eat i oranges, iteratively filling this table until we reach n. Each step looks at eating one orange or using divisibility options to reduce the count.

This solution in C uses a dynamic programming approach with a dp array of size n+1, which keeps track at each index of the minimum number of days needed to eat up to that many oranges. The solution sequentially calculates this for all oranges from 1 to n, considering all possible operations allowed per day.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), Space Complexity: O(n) due to the dp array usage.

Try this approach in the editor →

Approach 3: Memoization Search

According to the problem description, for each n, we can choose one of three ways:

  1. Decrease n by 1;
  2. If n can be divided by 2, divide the value of n by 2;
  3. If n can be divided by 3, divide the value of n by 3.

Therefore, the problem is equivalent to finding the minimum number of days to reduce n to 0 through the above three ways.

We design a function dfs(n), which represents the minimum number of days to reduce n to 0. The execution process of the function dfs(n) is as follows:

  1. If n < 2, return n;
  2. Otherwise, we can first reduce n to a multiple of 2 by n bmod 2 operations of 1, and then perform operation 2 to reduce n to n/2; we can also first reduce n to a multiple of 3 by n bmod 3 operations of 1, and then perform operation 3 to reduce n to n/3. We choose the minimum of the above two ways, that is, 1 + min(n bmod 2 + dfs(n/2), n bmod 3 + dfs(n/3)).

To avoid repeated calculations, we use the method of memoization search and store the calculated values of dfs(n) in a hash table.

The time complexity is O(log^2 n), and the space complexity is O(log^2 n).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive with Memoization

Time Complexity: O(log(n)), Space Complexity: O(n) due to stored results in memo array.

Dynamic Programming

Time Complexity: O(n), Space Complexity: O(n) due to the dp array usage.

Memoization Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive with MemoizationO(log n)O(log n)Best general solution when n can be extremely large. Uses division jumps and caching.
Bottom-Up Dynamic ProgrammingO(n)O(n)Good for understanding transitions or when n is small enough to allocate a DP table.

Video Solution

Minimum Number of Days to Eat N Oranges - Dynamic Programming - Leetcode 1553 - Python • NeetCode • 16,325 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Number of Days to Eat N Oranges easy or hard?
LeetCode classifies this problem as Hard because the optimal solution requires recognizing a mathematical shortcut and combining recursion with memoization. A naive DP approach is easy to write but fails for large n, while the optimized solution reduces the state space dramatically.
Minimum Number of Days to Eat N Oranges Python/Java solution
Both Python and Java implementations typically use a recursive function with a memoization map. Python uses a dictionary or functools.lru_cache, while Java uses a HashMap to store computed states. The recurrence 1 + min(n % 2 + f(n/2), n % 3 + f(n/3)) stays the same across languages.
How to solve Minimum Number of Days to Eat N Oranges in O(log n)?
Use a recursive function with memoization. For each value n, compute 1 + min(n % 2 + f(n/2), n % 3 + f(n/3)). The n % 2 or n % 3 represents the number of single-orange days needed to reach a divisible state. Store computed results in a hash map so each state is processed once.
What is the best approach for Minimum Number of Days to Eat N Oranges?
The most efficient solution uses recursion with memoization. Instead of subtracting one orange repeatedly, the algorithm jumps directly to states where n becomes divisible by 2 or 3 using n % 2 and n % 3 adjustments. Each computed state is cached in a hash map, reducing repeated work and giving roughly O(log n) time complexity.
Is Minimum Number of Days to Eat N Oranges asked at Google/Amazon/Meta?
This problem is commonly used in high-level algorithm interviews because it tests dynamic programming with state reduction and memoization. Variants or similar problems appear in interviews at companies like Google, Amazon, and Meta where candidates must optimize recursion using mathematical insights.
What data structure is used in Minimum Number of Days to Eat N Oranges?
The core data structure is a hash map (or dictionary) used for memoization. It stores previously computed results for f(n) so recursive calls reuse them instead of recomputing the same subproblems.
What is the time complexity of Minimum Number of Days to Eat N Oranges?
The optimal memoized recursion runs in about O(log n) time and O(log n) space because each recursive step divides n by 2 or 3 and cached states prevent recomputation. A naive dynamic programming approach that fills dp[1..n] would take O(n) time and O(n) space.

Ready to solve this problem?

Practice Minimum Number of Days to Eat N Oranges with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Regular Expression Matching