[Leetcode]1553. 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 (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.
Constraints:
1 <= n <= 2*10^9

Noticing that 1 <= n <= 2*10^9, we know that only O(logn) solutions would be accepted. If we apply the bottom-up dynamic programming directly, it’s O(n) and therefore would get TLE. Therefore, we need to modify it before the DP solution could be accepted.

This post will introduce two approaches: BFS and top-down dynamic programming.

BFS

As it’s asking for the minimum number of days, BFS could work because it would be able to generate the shortest path. It’s quite typical so I’ll skip the explanation and feel free to check intros to BFS here: Intro to Graph Algorithms – BFS & DFS.

class Solution:
    def minDays(self, n: int) -> int:
        q=[n]
        cnt = 0
        visited = set([])
        while q:
            new_q = []
            for e in q: 
                if e == 0:
                    return cnt
                if e-1 not in visited:
                    new_q.append(e-1)
                    visited.add(e-1)
                if e%2==0 and e//2 not in visited:
                    new_q.append(e//2)
                    visited.add(e//2)
                if e%3==0 and e//3 not in visited:
                    new_q.append(e//3)
                    visited.add(e//3)
            cnt += 1
            q = new_q
        return cnt

Dynamic Programming

To implement the DP approach, we have to notice that, we should always try to eat n/2 or n/3 apples when it’s possible, and we will never eat 1 apple for more than continuous 2 days. This proof is inspired from @yanrucheng.

If n-1-1-1 happens:

Proving that we could eat 1 apple for at most continuous 2 times

In this case, we need to implement a top-down approach and as we’d do n/2 and n/3 in most of the cases, the time complexity is reduced to O(logn).

class Solution:
    def minDays(self, n: int) -> int:
        @lru_cache(None)
        def helper(i=n):
            if i < 3:
                return i
            return min(i%2+helper(i//2),i%3+helper(i//3))+1
        return helper()
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments