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