noranges 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
1 <= n <= 2*10^9
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.
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
To implement the DP approach, we have to notice that, we should always try to eat
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.
In this case, we need to implement a top-down approach and as we’d do
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()