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
Solution: Greedy + DP
Eat oranges one by one to make it a multiply of 2 or 3 such that we can eat 50% or 66.66…% of the oranges in one step.
dp(n) := min steps to finish n oranges.
base case n <= 1, dp(n) = n
transition: dp(n) = 1 + min(n%2 + dp(n/2), n % 3 + dp(n / 3))
e.g. n = 11,
we eat 11%2 = 1 in one step, left = 10 and then eat 10 / 2 = 5 in another step. 5 left for the subproblem.
we eat 11%3 = 2 in two steps, left = 9 and then eat 9 * 2 / 3 = 6 in another step, 3 left for the subproblem.
dp(11) = 1 + min(1 + dp(5), 2 + dp(3))
T(n) = 2*T(n/2) + O(1) = O(n)
Time complexity: O(n) // w/o memoization, close to O(logn) in practice.
Space complexity: O(logn)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: int minDays(int n) { unordered_map<int, int> cache; function<int(int)> dp = [&](int n) { if (n <= 1) return n; auto it = cache.find(n); if (it != cache.end()) return it->second; return cache[n] = 1 + min(n % 2 + dp(n / 2), n % 3 + dp(n / 3)); }; return dp(n); } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution { private static Map<Integer, Integer> cache = new HashMap<>(); public int minDays(int n) { return dp(n); } private int dp(int n) { if (n <= 1) return n; if (cache.containsKey(n)) return cache.get(n); int ans = 1 + Math.min(n % 2 + dp(n / 2), n % 3 + dp(n / 3)); cache.put(n, ans); return ans; } } |
Python3
1 2 3 4 5 6 7 |
class Solution: def minDays(self, n: int) -> int: @lru_cache(None) def dp(n): if n <= 1: return n return 1 + min(n % 2 + dp(n // 2), n % 3 + dp(n // 3)) return dp(n) |
Solution 2: BFS
if x % 2 == 0, push x/2 onto the queue
if x % 3 == 0, push x/3 onto the queue
always push x – 1 onto the queue
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { public: int minDays(int n) { queue<int> q{{n}}; unordered_set<int> seen; int steps = 0; while (!q.empty()) { int size = q.size(); while (size--) { int x = q.front(); q.pop(); if (x == 0) return steps; if (x % 2 == 0 && seen.insert(x / 2).second) q.push(x / 2); if (x % 3 == 0 && seen.insert(x / 3).second) q.push(x / 3); if (seen.insert(x - 1).second) q.push(x - 1); } ++steps; } return -1; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment