Formatted question description: https://leetcode.ca/all/1553.html

# 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 = 10Output:4Explanation: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 = 6Output:3Explanation: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 = 1Output:1

**Example 4:**

Input:n = 56Output: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 `-1`

s.

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/
// 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);
}
};
```

Java

```
class Solution {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
public int minDays(int n) {
if (n <= 1)
return n;
if (map.containsKey(n))
return map.get(n);
int days = Math.min(minDays(n / 2) + n % 2 + 1, minDays(n / 3) + n % 3 + 1);
map.put(n, days);
return days;
}
}
```