Problem statement

https://leetcode.com/problems/minimum-number-of-days-to-eat-n-oranges/

Solution

Imagine that we do not have first option and instead when we have 3k+2 oranges we can go to k oranges making 3 steps. Then we can easily solve it with dp.

Complexity

Complexity is O(log N^2), because we have recurence T(n) = T(n//2) + T(n//3) + 1. Why? On the first level we have N, then we have N//2, N//3. Then we have N//2//2, N//2//3 = N//3//2, N//3//3. Here we use the property that N//a//b = N//b//a = N//a*b. On i-th level we have no more than i+1 values, and we can have O(log n) levels, so we have complexity like this.

Code

class Solution:
    def minDays(self, n):
        @lru_cache(None)
        def dp(i):
            if i <= 2: return i
            return min(dp(i//2) + i%2 + 1, dp(i//3) + i%3 + 1)
        
        return dp(n)