Minimum Number of Days to Eat N Oranges
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
nis divisible by2, then you can eatn / 2oranges. - If the number of remaining oranges
nis 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 = 10Output
4Starting with 10 oranges, one optimal sequence eats 1 orange, then 6 oranges, then 2 oranges, then the last orange, for a minimum of 4 days.
Example 2
Input
n = 6Output
3Starting with 6 oranges, one optimal sequence eats 3 oranges, then 2 oranges, then the last orange, for a minimum of 3 days.
Constraints
- 1 <= n <= 2 * 10^9