Welcome to Subscribe On Youtube
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 = 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 n1
, n/2
, n/3
cases and memoize the minimal value.
One caveat is that we shouldn’t do n1
case every time because that will regress our solution to O(N)
time complexity.
In fact, we should eat n % 2
oranges onebyone 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/minimumnumberofdaystoeatnoranges/
// 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);
}
};

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; } } ############ class Solution { private Map<Integer, Integer> f = new HashMap<>(); public int minDays(int n) { return dfs(n); } private int dfs(int n) { if (n < 2) { return n; } if (f.containsKey(n)) { return f.get(n); } int res = 1 + Math.min(n % 2 + dfs(n / 2), n % 3 + dfs(n / 3)); f.put(n, res); return res; } }

// OJ: https://leetcode.com/problems/minimumnumberofdaystoeatnoranges/ // 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); } };

class Solution: def minDays(self, n: int) > int: @cache def dfs(n): if n < 2: return n return 1 + min(n % 2 + dfs(n // 2), n % 3 + dfs(n // 3)) 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) } func min(a, b int) int { if a < b { return a } return b }