Minimum Number of Days to Eat N Oranges

Hard
1512.

Minimum Number of Days to Eat N Oranges

Minimum Number of Days to Eat N Oranges is a hard coding problem on dynamic programming and memoization, asked in Amazon and Google interviews.

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 n is divisible by 2, eat n / 2 oranges;
  • if n is divisible by 3, eat 2 * (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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var minDays = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 n is divisible by 2, eat n / 2 oranges;
  • if n is divisible by 3, eat 2 * (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

  1. Hint 1

    A table over every count up to n is far too large. Which counts can an optimal plan actually pass through?

  2. Hint 2

    Eating one orange at a time is only useful to reach a multiple of 2 or 3. Before halving, eat n % 2 singles; before taking two thirds, eat n % 3 singles — never more, because halving earlier would have been at least as good.

  3. 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 values n / (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

  1. Define days(0) = 0 and days(1) = 1.
  2. For larger x: days(x) = 1 + min(x % 2 + days(x / 2), x % 3 + days(x / 3)), using integer division.
  3. 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 leaving n / 3, so the recursion goes to n / 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