NeetCode #621LC-1553HardGraphs
← Back to All Problems#621 · #1553 · Minimum Number of Days to Eat N Oranges(吃掉 N 个橘子的最少天数)
📌 Problem Statement & Constraints
There are
n oranges. Each day you may: eat one orange, eat n/2 oranges if n is divisible by 2, or eat 2n/3 oranges if n is divisible by 3. Return the minimum number of days to eat all n oranges. Constraints: 1 <= n <= 2 * 10^9.💡 Core Algorithmic Approaches
- Memoised recursion on
n:f(n) = 1 + min(n % 2 + f(n // 2), n % 3 + f(n // 3)). - The
n % 2term is the number of single-orange days needed to makeneven before using the halving move. - The base cases are
f(0) = 0andf(1) = 1. - The
n // 2andn // 3recursion halves the state space, so the memo has only O(log n) distinct keys.
💻 Benchmark Python3 Implementation
class Solution:
def minDays(self, n: int) -> int:
memo = {}
def dfs(x: int) -> int:
if x <= 1:
return x # 0 oranges -> 0 days, 1 -> 1 day
if x in memo:
return memo[x]
# either make x even then halve, or make it divisible by 3 then take 2/3
res = 1 + min(x % 2 + dfs(x // 2), x % 3 + dfs(x // 3))
memo[x] = res
return res
return dfs(n)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(log n) distinct states, each O(1) work.
💾 Space Complexity
O(log n) for the memo and the recursion.
⚠️ Interview Pitfalls & Follow-ups
- BFS over all reachable values: the state space is too large for n up to 2 * 10^9.
- Forgetting the
x % 2cost: making an odd number even costs single-orange days. - Using
x // 2when x is odd: the halving move requires divisibility, hence thex % 2adjustment. - Not memoising: the recursion would branch exponentially.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.