Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Minimum Number of Days to Eat N Oranges solution and explanation

HardDynamic ProgrammingMemoization6 min read36.2% acceptanceUpdated 9 Apr 2026
Asked atGoogle
Practise Minimum Number of Days to Eat N Oranges
16:51
Minimum Number of Days to Eat N Oranges - Dynamic Programming - Leetcode 1553 - PythonNeetCode · 16:51 · 16K viewsWatch on YouTube
9 more videos on this problem
  1. Minimum Number of Days to Eat N Oranges - Dynamic Programming - Leetcode 1553 - PythonNeetCode · 16:51 · 16K views
  2. 花花酱 LeetCode 1553. Minimum Number of Days to Eat N Oranges - 刷题找工作 EP350Hua Hua · 16:16 · 1K views
  3. Minimum Number of Days to Eat N Oranges | Leet code 1553 | Theory explained + Python codeSai Anish Malla · 15:33 · 1K views
  4. 1553. Minimum Number of Days to Eat N Oranges (Leetcode Hard)Programming Live with Larry · 10:58 · 829 views
  5. 1553. Minimum Number of Days to Eat N Oranges | LeetCode Weekly Contest 202 | DP | MemoizationCoding Gist · 7:03 · 475 views
  6. LeetCode 1553. Minimum Number of Days to Eat N OrangesHappy Coding · 34:18 · 399 views
  7. 【每日一题】1553. Minimum Number of Days to Eat N Oranges, 8/17/2020Huifeng Guan · 23:00 · 341 views
  8. LeetCode #1553 - Minimum Number of Days to Eat N Oranges: Dynamic ProgrammingGDSC FIU · 10:37 · 245 views
  9. Leetcode weekly contest 202 | Problem 4 | Minimum Number of Days to Eat N OrangesCP Addict · 3:53 · 137 views
  10. Leetcode 1553. Minimum Number of Days to Eat N OrangesFearless Learner · 4:06 · 30 views

The problem

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.

from functools import lru_cache

class Solution:
    @lru_cache(None)
    def minDays(self, n: int) -> int:
        if n <= 1:
            return n
        return 1 + min(n % 2 + self.minDays(n // 2), n % 3 + self.minDays(n // 3))

sol = Solution()
print(sol.minDays(10)) # Output: 4
import java.util.HashMap;

public class Solution {
    private HashMap<Integer, Integer> memo = new HashMap<>();

    public int minDaysHelper(int n) {
        if (n <= 1) return n;
        if (memo.containsKey(n)) return memo.get(n);
        int result = 1 + Math.min(n % 2 + minDaysHelper(n / 2), n % 3 + minDaysHelper(n / 3));
        memo.put(n, result);
        return result;
    }

    public int minDays(int n) {
        return minDaysHelper(n);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minDays(10)); // Output: 4
    }
}
#include <iostream>
#include <unordered_map>

int minDaysHelper(int n, std::unordered_map<int, int>& memo) {
    if (n <= 1) return n;
    if (memo.find(n) != memo.end()) return memo[n];
    int result = 1 + std::min(n % 2 + minDaysHelper(n / 2, memo), n % 3 + minDaysHelper(n / 3, memo));
    memo[n] = result;
    return result;
}

int minDays(int n) {
    std::unordered_map<int, int> memo;
    return minDaysHelper(n, memo);
}

int main() {
    int n = 10;
    std::cout << minDays(n) << std::endl; // Output: 4
    return 0;
}
const minDays = (n, memo = new Map()) => {
    if (n <= 1) return n;
    if (memo.has(n)) return memo.get(n);
    const result = 1 + Math.min(n % 2 + minDays(Math.floor(n / 2), memo), n % 3 + minDays(Math.floor(n / 3), memo));
    memo.set(n, result);
    return result;
};

console.log(minDays(10)); // Output: 4
#include <stdio.h>
#include <stdlib.h>

int minDaysHelper(int n, int* memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    int eatOne = 1 + minDaysHelper(n - 1, memo);
    int eatHalf = n % 2 == 0 ? 1 + minDaysHelper(n / 2, memo) : INT_MAX;
    int eatTwoThirds = n % 3 == 0 ? 1 + minDaysHelper(n / 3, memo) : INT_MAX;
    int result = (eatOne < eatHalf) ? ((eatOne < eatTwoThirds) ? eatOne : eatTwoThirds) : ((eatHalf < eatTwoThirds) ? eatHalf : eatTwoThirds);
    memo[n] = result;
    return result;
}

int minDays(int n) {
    int* memo = (int*)calloc(n + 1, sizeof(int));
    int result = minDaysHelper(n, memo);
    free(memo);
    return result;
}

int main() {
    int n = 10;
    printf("%d\n", minDays(n)); // Output: 4
    return 0;
}
using System;
using System.Collections.Generic;

public class Solution {
    private Dictionary<int, int> memo = new Dictionary<int, int>();

    public int MinDaysHelper(int n) {
        if (n <= 1) return n;
        if (memo.ContainsKey(n)) return memo[n];
        int result = 1 + Math.Min(n % 2 + MinDaysHelper(n / 2), n % 3 + MinDaysHelper(n / 3));
        memo[n] = result;
        return result;
    }

    public int MinDays(int n) {
        return MinDaysHelper(n);
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine(sol.MinDays(10)); // Output: 4
    }
}

This Python solution uses the LRU cache to memoize results of subproblems. We recursively determine the minimum number of days needed by considering every operation, storing results as we progress.

Complexity

Time Complexity: O(log(n)), Space Complexity: O(log(n)) due to the space used by the cache.

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.

def minDays(n: int) -> int:
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i - 1] + 1
        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i // 2] + 1)
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i // 3] + 1)
    return dp[n]

print(minDays(10)) # Output: 4
public class Solution {
    public int minDays(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minDays(10)); // Output: 4
    }
}
#include <iostream>
#include <vector>

int minDays(int n) {
    std::vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1] + 1;
        if (i % 2 == 0) dp[i] = std::min(dp[i], dp[i / 2] + 1);
        if (i % 3 == 0) dp[i] = std::min(dp[i], dp[i / 3] + 1);
    }
    return dp[n];
}

int main() {
    int n = 10;
    std::cout << minDays(n) << std::endl; // Output: 4
    return 0;
}
const minDays = (n) => {
    let dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= n; i++) {
        dp[i] = dp[i - 1] + 1;
        if (i % 2 === 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
        if (i % 3 === 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
    }
    return dp[n];
};

console.log(minDays(10)); // Output: 4
#include <stdio.h>
#include <stdlib.h>

int minDays(int n) {
    int* dp = (int*)malloc((n + 1) * sizeof(int));
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1] + 1;
        if (i % 2 == 0) dp[i] = dp[i] < dp[i / 2] + 1 ? dp[i] : dp[i / 2] + 1;
        if (i % 3 == 0) dp[i] = dp[i] < dp[i / 3] + 1 ? dp[i] : dp[i / 3] + 1;
    }
    int result = dp[n];
    free(dp);
    return result;
}

int main() {
    int n = 10;
    printf("%d\n", minDays(n)); // Output: 4
    return 0;
}
using System;

public class Solution {
    public int MinDays(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            if (i % 2 == 0) dp[i] = Math.Min(dp[i], dp[i / 2] + 1);
            if (i % 3 == 0) dp[i] = Math.Min(dp[i], dp[i / 3] + 1);
        }
        return dp[n];
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine(sol.MinDays(10)); // Output: 4
    }
}

The Python solution employs a dynamic programming strategy with an array to hold the best solution iteratively for each number of oranges. The solution checks each potential choice each day and writes to dp the best move.

Complexity

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

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

function minDays(n: number): number {
    const f: Record<number, number> = {};
    const dfs = (n: number): number => {
        if (n < 2) {
            return n;
        }
        if (f[n] !== undefined) {
            return f[n];
        }
        f[n] = 1 + Math.min((n % 2) + dfs((n / 2) | 0), (n % 3) + dfs((n / 3) | 0));
        return f[n];
    };
    return dfs(n);
}
func minDays(n int) int {
	f := map[int]int{0: 0, 1: 1}
	var dfs func(int) int
	dfs = func(n int) int {
		if v, ok := f[n]; ok {
			return v
		}
		res := 1 + min(n%2+dfs(n/2), n%3+dfs(n/3))
		f[n] = res
		return res
	}
	return dfs(n)
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Recursive with Memoization

Time Complexity: O(log(n)), Space Complexity: O(log(n)) due to the space used by the cache.

Dynamic Programming

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

Memoization Search–

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.

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.

Comments

Now write it yourselfClose this page and solve Minimum Number of Days to Eat N Oranges in the editor, without looking.
Practise Minimum Number of Days to Eat N Oranges