1553

1553. Minimum Number of Days to Eat N Oranges (Hard)

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.

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.

Example 3:

Input: n = 1
Output: 1

Example 4:

Input: n = 56
Output: 6

 

Constraints:

• 1 <= n <= 2*10^9

Related Topics:
Dynamic Programming

Solution 1. DP

The idea of the solution is not hard -- basically use DFS to try n-1, n/2, n/3 cases and memoize the minimal value.

One caveat is that we shouldn't do n-1 case every time because that will regress our solution to O(N) time complexity.

In fact, we should eat n % 2 oranges one-by-one and then swallow n / 2, or eat n % 3 oranges so that we can gobble 2 * n / 3.

We need to prove that this works. This solution can be expressed as "we should never take more than 2 consecutive -1 operations".

We can prove by contradiction:

Assume there exits some n that we need to take 3 consecutive -1 operations for optimal solution, i.e. minDays(n) = minDays(n - 3) + 3.

If the first operation we take for n - 3 is /2, then n is odd. Since (n - 3) / 2 = (n - 1) / 2 - 1, we can see that taking -1, /2, -1 3 operations is better than taking -1, -1, -1, /2 4 operations. So taking 3 -1 operations is not optimal in this case.

If the first operation we take for n - 3 is /3, so n is divisible by 3. Since (n - 3) / 3 = n / 3 - 1, we can see that taking /3, -1 2 operations is better than taking -1, -1, -1, /3 4 operations. So taking 3 -1 operations is not optimal in this case.

This process can be extended to taking k >= 3 consecutive -1s.

Thus the conclusion is taht we should always at most take 2 consecutive -1 operations.

// OJ: https://leetcode.com/problems/minimum-number-of-days-to-eat-n-oranges/
// Author: github.com/lzl124631x
// Time: O(logN)
// Space: O(logN)
class Solution {
    unordered_map<int, int> m;
public:
    int minDays(int n) {
        if (n <= 1) return n;
        if (m.count(n)) return m[n];
        return m[n] = 1 + min(minDays(n / 3) + n % 3, minDays(n / 2) + n % 2);
    }
};