Minimum Number of Days to Eat N Oranges — LeetCode 1553 Python Solution

The problem

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.

Example

Input

n = 10

Output

4

Explanation

You have 10 oranges.

Python solution

class Solution:
    def minDays(self, n: int) -> int:
        @cache
        def dfs(n: int) -> int:
            if n < 2:
                return n
            return 1 + min(n % 2 + dfs(n // 2), n % 3 + dfs(n // 3))

        return dfs(n)

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1553. Minimum Number of Days to Eat N Oranges is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming and Memoization.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems