Minimum Number of Days to Eat N Oranges — Problem & Solution
Minimum Number of Days to Eat N Oranges solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimum Number of Days to Eat N Oranges is a hard coding problem on dynamic programming and memoization, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Dynamic Programming, Memoization
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n oranges in the kitchen. Each day you eat some of them, choosing exactly one of these options for the day (with n the number of oranges left that morning):
- eat one orange;
- if
nis divisible by 2, eatn / 2oranges; - if
nis divisible by 3, eat2 * (n / 3)oranges.
Return the minimum number of days needed to eat all n oranges.
Example 1
Input: n = 1
Output: 1
Example 2
Input: n = 10
Output: 4
Explanation: 10 → 9 (eat one) → 3 (eat two thirds) → 1 (eat two thirds) → 0.
Example 3
Input: n = 56
Output: 6
Explanation: 56 → 28 → 14 → 7 → 6 → 2 → 0 is one six-day plan; there is no five-day plan.
Constraints
1 <= n <= 2 * 10^9
Hints for Minimum Number of Days to Eat N Oranges
Hint 1
A table over every count up to
nis far too large. Which counts can an optimal plan actually pass through?Hint 2
Eating one orange at a time is only useful to reach a multiple of 2 or 3. Before halving, eat
n % 2singles; before taking two thirds, eatn % 3singles — never more, because halving earlier would have been at least as good.Hint 3
So
days(n) = 1 + min(n % 2 + days(n / 2), n % 3 + days(n / 3))with integer division,days(0) = 0,days(1) = 1. Memoise it — only O(log² n) distinct valuesn / (2^a · 3^b)ever appear.
How to solve Minimum Number of Days to Eat N Oranges
Single-orange days are only worth spending to reach the next multiple of 2 or 3. That turns the huge state space into the values floor(n / (2^a · 3^b)), of which there are only about log2 n · log3 n.
Approach
- Define
days(0) = 0anddays(1) = 1. - For larger
x:days(x) = 1 + min(x % 2 + days(x / 2), x % 3 + days(x / 3)), using integer division. - Memoise in a hash map and return
days(n).
Why it works
In an optimal plan, look at the first day that halves or takes two thirds. Every single-orange day before it can be rearranged: if more than x % 2 singles precede a halving, two of them could be traded for one single after it (eating 2 before halving removes the same as eating 1 after), which never costs more. The same exchange with three singles works for the two-thirds move. So an optimal plan eats exactly x % 2 or x % 3 singles and then divides, which is the recurrence; since floor(floor(x/2)/3) = floor(x/6), every state is n divided by some 2^a · 3^b.
Complexity
- Time —
O(log² n) - Space —
O(log² n)
Pitfalls
- A bottom-up array or a BFS over all counts up to 2 · 10^9 runs out of memory and time.
- Including 'eat one' as its own recursive branch (
days(x - 1)) brings back the linear state space. - Two-thirds means eating
2 * (n / 3)and leavingn / 3, so the recursion goes ton / 3.
Reference solution
Python
def minDays(n: int) -> int:
memo = {0: 0, 1: 1}
def days(x):
if x in memo:
return memo[x]
r = 1 + min(x % 2 + days(x // 2), x % 3 + days(x // 3))
memo[x] = r
return r
return days(n)Java
static int orangeDays(int x, Map<Integer, Integer> memo) {
if (x <= 1) return x;
Integer hit = memo.get(x);
if (hit != null) return hit;
int r = 1 + Math.min(x % 2 + orangeDays(x / 2, memo), x % 3 + orangeDays(x / 3, memo));
memo.put(x, r);
return r;
}
public static int minDays(int n) {
return orangeDays(n, new HashMap<>());
}C++
int orangeDays(int x, unordered_map<int, int>& memo) {
if (x <= 1) return x;
auto it = memo.find(x);
if (it != memo.end()) return it->second;
int r = 1 + min(x % 2 + orangeDays(x / 2, memo), x % 3 + orangeDays(x / 3, memo));
memo[x] = r;
return r;
}
int minDays(int n) {
unordered_map<int, int> memo;
return orangeDays(n, memo);
}JavaScript
var minDays = function(n) {
var memo = new Map();
memo.set(0, 0);
memo.set(1, 1);
var days = function(x) {
var hit = memo.get(x);
if (hit !== undefined) return hit;
var r = 1 + Math.min(x % 2 + days(Math.floor(x / 2)), x % 3 + days(Math.floor(x / 3)));
memo.set(x, r);
return r;
};
return days(n);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming