1553. Minimum Number of Days to Eat N Oranges
Description
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 by2
then you can eatn / 2
oranges. - If the number of remaining oranges
n
is divisible by3
then you can eat2 * (n / 3)
oranges.
You can only choose one of the actions per day.
Given the integer n
, 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.
Constraints:
1 <= n <= 2 * 109
Solutions
Solution 1: Memoization Search
According to the problem description, for each $n$, we can choose one of three ways:
- Decrease $n$ by $1$;
- If $n$ can be divided by $2$, divide the value of $n$ by $2$;
- If $n$ can be divided by $3$, divide the value of $n$ by $3$.
Therefore, the problem is equivalent to finding the minimum number of days to reduce $n$ to $0$ through the above three ways.
We design a function $dfs(n)$, which represents the minimum number of days to reduce $n$ to $0$. The execution process of the function $dfs(n)$ is as follows:
- If $n < 2$, return $n$;
- Otherwise, we can first reduce $n$ to a multiple of $2$ by $n \bmod 2$ operations of $1$, and then perform operation $2$ to reduce $n$ to $n/2$; we can also first reduce $n$ to a multiple of $3$ by $n \bmod 3$ operations of $1$, and then perform operation $3$ to reduce $n$ to $n/3$. We choose the minimum of the above two ways, that is, $1 + \min(n \bmod 2 + dfs(n/2), n \bmod 3 + dfs(n/3))$.
To avoid repeated calculations, we use the method of memoization search and store the calculated values of $dfs(n)$ in a hash table.
The time complexity is $O(\log^2 n)$, and the space complexity is $O(\log^2 n)$.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|