⚡Flashcard Drill➔
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

  1. Memoised recursion on n: f(n) = 1 + min(n % 2 + f(n // 2), n % 3 + f(n // 3)).
  2. The n % 2 term is the number of single-orange days needed to make n even before using the halving move.
  3. The base cases are f(0) = 0 and f(1) = 1.
  4. The n // 2 and n // 3 recursion 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 % 2 cost: making an odd number even costs single-orange days.
  • Using x // 2 when x is odd: the halving move requires divisibility, hence the x % 2 adjustment.
  • 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems