1553. Minimum Number of Days to Eat N Oranges - Explanation

Description

You have n oranges. Each day you must choose exactly one of the following actions:

Eat one orange.
If the current number of oranges is divisible by 2, eat half of them.
If the current number is divisible by 3, eat two thirds of them.

Return the fewest days needed to eat every orange.

Example 1:

Input: n = 3

Output: 2

Explanation: Eat two oranges on the first day using the divisible-by-3 action, then eat the last orange on the second day.

Example 2:

Input: n = 4

Output: 3

Explanation: Eat half to leave two oranges, then one orange on each of the next two days. Three days are necessary.

Example 3:

Input: n = 1

Output: 1

Explanation: Eat the only orange in one day.

Constraints:

1 <= n <= 2000000000

Topics

Dynamic Programming Memoization

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Dynamic Programming (Memoization) - Caching recursive results to avoid redundant computation
Recursion - Breaking down problems into smaller subproblems with base cases
BFS (Breadth-First Search) - Finding shortest paths in unweighted graphs by exploring level by level
Greedy Algorithms - Making locally optimal choices to reach a global optimum

1. Dynamic Programming (Top-Down)

Intuition

At each step, we can eat one orange, half the oranges (if divisible by 2), or two-thirds of the oranges (if divisible by 3). A naive recursion explores all three options at each state and picks the minimum.

The challenge is that n can be very large, but memoization helps by caching results for previously computed values. However, this approach still explores too many states because eating one orange at a time creates many intermediate values.

Algorithm

Use a hash map to memoize results for each value of n.
Base case: if n is 0, return 0 (no days needed).
For each state, compute the minimum of:
- Eating one orange and solving for n - 1
- If divisible by 2, eating half and solving for n / 2
- If divisible by 3, eating two-thirds and solving for n / 3
Store and return the minimum result plus one day.

class Solution:
    def minDays(self, n: int) -> int:
        dp = {}

        def dfs(n):
            if n == 0:
                return 0
            if n in dp:
                return dp[n]

            res = 1 + dfs(n - 1)
            if n % 3 == 0:
                res = min(res, 1 + dfs(n // 3))
            if n % 2 == 0:
                res = min(res, 1 + dfs(n // 2))

            dp[n] = res
            return res

        return dfs(n)

public class Solution {
    private Map<Integer, Integer> dp = new HashMap<>();

    public int minDays(int n) {
        return dfs(n);
    }

    private int dfs(int n) {
        if (n == 0) return 0;
        if (dp.containsKey(n)) return dp.get(n);

        int res = 1 + dfs(n - 1);
        if (n % 3 == 0) res = Math.min(res, 1 + dfs(n / 3));
        if (n % 2 == 0) res = Math.min(res, 1 + dfs(n / 2));

        dp.put(n, res);
        return res;
    }
}

class Solution {
public:
    unordered_map<int, int> dp;

    int minDays(int n) {
        return dfs(n);
    }

    int dfs(int n) {
        if (n == 0) return 0;
        if (dp.count(n)) return dp[n];

        int res = 1 + dfs(n - 1);
        if (n % 3 == 0) res = min(res, 1 + dfs(n / 3));
        if (n % 2 == 0) res = min(res, 1 + dfs(n / 2));

        return dp[n] = res;
    }
};

class Solution {
    /**
     * @param {number} n
     * @return {number}
     */
    minDays(n) {
        const dp = new Map();

        const dfs = (n) => {
            if (n === 0) return 0;
            if (dp.has(n)) return dp.get(n);

            let res = 1 + dfs(n - 1);
            if (n % 3 === 0) res = Math.min(res, 1 + dfs(n / 3));
            if (n % 2 === 0) res = Math.min(res, 1 + dfs(n / 2));

            dp.set(n, res);
            return res;
        };

        return dfs(n);
    }
}

public class Solution {
    private Dictionary<int, int> dp = new Dictionary<int, int>();

    public int MinDays(int n) {
        return Dfs(n);
    }

    private int Dfs(int n) {
        if (n == 0) return 0;
        if (dp.ContainsKey(n)) return dp[n];

        int res = 1 + Dfs(n - 1);
        if (n % 3 == 0) res = Math.Min(res, 1 + Dfs(n / 3));
        if (n % 2 == 0) res = Math.Min(res, 1 + Dfs(n / 2));

        dp[n] = res;
        return res;
    }
}

func minDays(n int) int {
    dp := make(map[int]int)

    var dfs func(n int) int
    dfs = func(n int) int {
        if n == 0 {
            return 0
        }
        if val, ok := dp[n]; ok {
            return val
        }

        res := 1 + dfs(n-1)
        if n%3 == 0 {
            res = min(res, 1+dfs(n/3))
        }
        if n%2 == 0 {
            res = min(res, 1+dfs(n/2))
        }

        dp[n] = res
        return res
    }

    return dfs(n)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

class Solution {
    private val dp = hashMapOf<Int, Int>()

    fun minDays(n: Int): Int {
        return dfs(n)
    }

    private fun dfs(n: Int): Int {
        if (n == 0) return 0
        if (n in dp) return dp[n]!!

        var res = 1 + dfs(n - 1)
        if (n % 3 == 0) res = minOf(res, 1 + dfs(n / 3))
        if (n % 2 == 0) res = minOf(res, 1 + dfs(n / 2))

        dp[n] = res
        return res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Greedy + Dynamic Programming (Top-Down)

Intuition

The key optimization is recognizing that we should always try to divide rather than subtract one repeatedly. Instead of exploring n - 1 recursively (which creates exponentially many states), we can directly compute how many subtractions are needed to reach a divisible number.

To reach a number divisible by 2, we need n % 2 subtractions. To reach a number divisible by 3, we need n % 3 subtractions. By adding these remainder costs upfront, we only need to recurse on n / 2 and n / 3, drastically reducing the state space to O(log n).

Algorithm

Use a hash map with base cases: 0 oranges takes 0 days, 1 orange takes 1 day.
For each state n:
- Compute cost to divide by 2: (n % 2) remainder days + 1 division day + solve for n / 2
- Compute cost to divide by 3: (n % 3) remainder days + 1 division day + solve for n / 3
- Take the minimum of both options.
Memoize and return the result.

class Solution:
    def minDays(self, n: int) -> int:
        dp = {0: 0, 1: 1}

        def dfs(n):
            if n in dp:
                return dp[n]

            res = 1 + (n % 2) + dfs(n // 2)
            res = min(res, 1 + (n % 3) + dfs(n // 3))
            dp[n] = res
            return res

        return dfs(n)

public class Solution {
    private Map<Integer, Integer> dp = new HashMap<>();

    public int minDays(int n) {
        dp.put(0, 0);
        dp.put(1, 1);
        return dfs(n);
    }

    private int dfs(int n) {
        if (dp.containsKey(n)) return dp.get(n);

        int res = 1 + (n % 2) + dfs(n / 2);
        res = Math.min(res, 1 + (n % 3) + dfs(n / 3));

        dp.put(n, res);
        return res;
    }
}

class Solution {
public:
    unordered_map<int, int> dp;

    int minDays(int n) {
        dp[0] = 0;
        dp[1] = 1;
        return dfs(n);
    }

private:
    int dfs(int n) {
        if (dp.count(n)) return dp[n];

        int res = 1 + (n % 2) + dfs(n / 2);
        res = min(res, 1 + (n % 3) + dfs(n / 3));

        return dp[n] = res;
    }
};

class Solution {
    /**
     * @param {number} n
     * @return {number}
     */
    minDays(n) {
        const dp = new Map();
        dp.set(0, 0);
        dp.set(1, 1);

        const dfs = (n) => {
            if (dp.has(n)) return dp.get(n);

            let res = 1 + (n % 2) + dfs(Math.floor(n / 2));
            res = Math.min(res, 1 + (n % 3) + dfs(Math.floor(n / 3)));

            dp.set(n, res);
            return res;
        };

        return dfs(n);
    }
}

public class Solution {
    private Dictionary<int, int> dp = new Dictionary<int, int>();

    public int MinDays(int n) {
        dp[0] = 0;
        dp[1] = 1;
        return Dfs(n);
    }

    private int Dfs(int n) {
        if (dp.ContainsKey(n)) return dp[n];

        int res = 1 + (n % 2) + Dfs(n / 2);
        res = Math.Min(res, 1 + (n % 3) + Dfs(n / 3));

        dp[n] = res;
        return res;
    }
}

func minDays(n int) int {
    dp := map[int]int{0: 0, 1: 1}

    var dfs func(n int) int
    dfs = func(n int) int {
        if val, ok := dp[n]; ok {
            return val
        }

        res := 1 + (n % 2) + dfs(n/2)
        res = min(res, 1+(n%3)+dfs(n/3))

        dp[n] = res
        return res
    }

    return dfs(n)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

class Solution {
    private val dp = hashMapOf(0 to 0, 1 to 1)

    fun minDays(n: Int): Int {
        return dfs(n)
    }

    private fun dfs(n: Int): Int {
        if (n in dp) return dp[n]!!

        var res = 1 + (n % 2) + dfs(n / 2)
        res = minOf(res, 1 + (n % 3) + dfs(n / 3))

        dp[n] = res
        return res
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(\log n)$

3. Breadth First Search

Intuition

BFS naturally finds the shortest path in an unweighted graph. Here, each state (number of oranges) is a node, and each valid operation is an edge. Since all edges have equal cost (one day), BFS will find the minimum days when we first reach 0.

We use a visited set to avoid reprocessing the same orange count. From each state, we explore eating one orange, and optionally dividing by 2 or 3 if applicable.

Algorithm

Initialize a queue with n and a visited set.
Process level by level (each level represents one day):
- For each current orange count, try all three operations.
- If any operation results in 0, return the current day count.
- Add unvisited new states to the queue.
Continue until reaching 0.

class Solution:
    def minDays(self, n: int) -> int:
        q = deque([n])
        visit = set()
        res = 0

        while q:
            res += 1
            for _ in range(len(q)):
                node = q.popleft()
                nei = node - 1
                if nei == 0:
                    return res
                if nei not in visit:
                    visit.add(nei)
                    q.append(nei)
                for d in range(2, 4):
                    if node % d == 0:
                        nei = node // d
                        if nei == 0:
                            return res
                        if nei not in visit:
                            visit.add(nei)
                            q.append(nei)
        return res

public class Solution {
    public int minDays(int n) {
        Queue<Integer> q = new LinkedList<>();
        Set<Integer> visit = new HashSet<>();
        q.offer(n);
        int res = 0;

        while (!q.isEmpty()) {
            res++;
            for (int i = q.size(); i > 0; i--) {
                int node = q.poll();
                int nei = node - 1;
                if (nei == 0) return res;
                if (!visit.contains(nei)) {
                    visit.add(nei);
                    q.offer(nei);
                }
                for (int d = 2; d <= 3; d++) {
                    if (node % d == 0) {
                        nei = node / d;
                        if (nei == 0) return res;
                        if (!visit.contains(nei)) {
                            visit.add(nei);
                            q.offer(nei);
                        }
                    }
                }
            }
        }
        return res;
    }
}

class Solution {
public:
    int minDays(int n) {
        queue<int> q;
        unordered_set<int> visit;
        q.push(n);
        int res = 0;

        while (!q.empty()) {
            res++;
            for (int i = q.size(); i > 0; i--) {
                int node = q.front(); q.pop();
                int nei = node - 1;
                if (nei == 0) return res;
                if (visit.find(nei) == visit.end()) {
                    visit.insert(nei);
                    q.push(nei);
                }
                for (int d = 2; d <= 3; d++) {
                    if (node % d == 0) {
                        nei = node / d;
                        if (nei == 0) return res;
                        if (visit.find(nei) == visit.end()) {
                            visit.insert(nei);
                            q.push(nei);
                        }
                    }
                }
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number} n
     * @return {number}
     */
    minDays(n) {
        const q = new Queue([n]);
        const visit = new Set();
        let res = 0;

        while (!q.isEmpty()) {
            res++;
            for (let i = q.size(); i > 0; i--) {
                let node = q.pop();
                let nei = node - 1;
                if (nei === 0) return res;
                if (!visit.has(nei)) {
                    visit.add(nei);
                    q.push(nei);
                }
                for (let d = 2; d <= 3; d++) {
                    if (node % d === 0) {
                        nei = Math.floor(node / d);
                        if (nei === 0) return res;
                        if (!visit.has(nei)) {
                            visit.add(nei);
                            q.push(nei);
                        }
                    }
                }
            }
        }
        return res;
    }
}

public class Solution {
    public int MinDays(int n) {
        Queue<int> q = new Queue<int>();
        HashSet<int> visit = new HashSet<int>();
        q.Enqueue(n);
        int res = 0;

        while (q.Count > 0) {
            res++;
            for (int i = q.Count; i > 0; i--) {
                int node = q.Dequeue();
                int nei = node - 1;
                if (nei == 0) return res;
                if (!visit.Contains(nei)) {
                    visit.Add(nei);
                    q.Enqueue(nei);
                }
                for (int d = 2; d <= 3; d++) {
                    if (node % d == 0) {
                        nei = node / d;
                        if (nei == 0) return res;
                        if (!visit.Contains(nei)) {
                            visit.Add(nei);
                            q.Enqueue(nei);
                        }
                    }
                }
            }
        }
        return res;
    }
}

func minDays(n int) int {
    q := []int{n}
    visit := make(map[int]bool)
    res := 0

    for len(q) > 0 {
        res++
        for i := len(q); i > 0; i-- {
            node := q[0]
            q = q[1:]
            nei := node - 1
            if nei == 0 {
                return res
            }
            if !visit[nei] {
                visit[nei] = true
                q = append(q, nei)
            }
            for d := 2; d <= 3; d++ {
                if node%d == 0 {
                    nei = node / d
                    if nei == 0 {
                        return res
                    }
                    if !visit[nei] {
                        visit[nei] = true
                        q = append(q, nei)
                    }
                }
            }
        }
    }
    return res
}

class Solution {
    fun minDays(n: Int): Int {
        val q = ArrayDeque<Int>()
        val visit = hashSetOf<Int>()
        q.addLast(n)
        var res = 0

        while (q.isNotEmpty()) {
            res++
            repeat(q.size) {
                val node = q.removeFirst()
                var nei = node - 1
                if (nei == 0) return res
                if (nei !in visit) {
                    visit.add(nei)
                    q.addLast(nei)
                }
                for (d in 2..3) {
                    if (node % d == 0) {
                        nei = node / d
                        if (nei == 0) return res
                        if (nei !in visit) {
                            visit.add(nei)
                            q.addLast(nei)
                        }
                    }
                }
            }
        }
        return res
    }
}

class Solution {
    func minDays(_ n: Int) -> Int {
        var q = [n]
        var visit = Set<Int>()
        var res = 0

        while !q.isEmpty {
            res += 1
            for _ in 0..<q.count {
                let node = q.removeFirst()
                var nei = node - 1
                if nei == 0 { return res }
                if !visit.contains(nei) {
                    visit.insert(nei)
                    q.append(nei)
                }
                for d in 2...3 {
                    if node % d == 0 {
                        nei = node / d
                        if nei == 0 { return res }
                        if !visit.contains(nei) {
                            visit.insert(nei)
                            q.append(nei)
                        }
                    }
                }
            }
        }
        return res
    }
}

impl Solution {
    pub fn min_days(n: i32) -> i32 {
        let mut q = VecDeque::new();
        let mut visit = HashSet::new();
        q.push_back(n);
        let mut res = 0;

        while !q.is_empty() {
            res += 1;
            for _ in 0..q.len() {
                let node = q.pop_front().unwrap();
                let nei = node - 1;
                if nei == 0 { return res; }
                if visit.insert(nei) {
                    q.push_back(nei);
                }
                for d in 2..=3 {
                    if node % d == 0 {
                        let nei = node / d;
                        if nei == 0 { return res; }
                        if visit.insert(nei) {
                            q.push_back(nei);
                        }
                    }
                }
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(\log n)$

Common Pitfalls

Recursing on n-1 Directly Causes TLE

The naive approach of recursively calling dfs(n-1) for the "eat one orange" option explores O(n) states, causing Time Limit Exceeded for large inputs. The key optimization is to never recurse on n-1 directly. Instead, compute the cost to reach the nearest divisible number: (n % 2) + 1 + dfs(n // 2) or (n % 3) + 1 + dfs(n // 3). This reduces the state space from O(n) to O(log n).

Missing Base Cases in Memoization

The optimized solution requires explicit base cases for n = 0 and n = 1 before computing the recursive formula. Forgetting dp[1] = 1 will cause infinite recursion or incorrect results since the formula 1 + (n % 2) + dfs(n // 2) does not naturally terminate at 1. Always initialize the memoization cache with {0: 0, 1: 1}.

Integer Division Confusion Across Languages

In the optimized recurrence, you compute dfs(n // 2) and dfs(n // 3). Be careful with integer division semantics. In Python, // performs floor division. In JavaScript, you need Math.floor(n / 2). Using regular division / in languages like JavaScript or Python 2 will produce floating-point results, causing cache misses and incorrect behavior.

Forgetting That All Three Options Must Be Considered

Even in the optimized solution, you must consider both paths: reducing to a multiple of 2 and reducing to a multiple of 3. Some solutions incorrectly assume one division is always better. For example, with n = 7, going via 6 (divide by 3) takes 3 days, but going via 6 then 3 then 1 needs careful comparison. Always take the minimum of both division paths.