Minimum Number of Days to Eat N Oranges

Hard

#1430Time: Exponential. The function branches into two calls for `n/2` and `n/3`, leading to a large number of redundant computations. This will result in a "Time Limit Exceeded" error for the given constraints.Space: `O(log n)` due to the maximum depth of the recursion stack.

Patterns

Dynamic Programming Memoization

Prompt

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.

Given the integer n, return the minimum number of days to eat n oranges.

Example 1:

Input: n = 10
Output: 4
Explanation: You have 10 oranges.
Day 1: Eat 1 orange,  10 - 1 = 9.  
Day 2: Eat 6 oranges, 9 - 2*(9/3) = 9 - 6 = 3. (Since 9 is divisible by 3)
Day 3: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. 
Day 4: Eat the last orange  1 - 1  = 0.
You need at least 4 days to eat the 10 oranges.

Example 2:

Input: n = 6
Output: 3
Explanation: You have 6 oranges.
Day 1: Eat 3 oranges, 6 - 6/2 = 6 - 3 = 3. (Since 6 is divisible by 2).
Day 2: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. (Since 3 is divisible by 3)
Day 3: Eat the last orange  1 - 1  = 0.
You need at least 3 days to eat the 6 oranges.

Constraints:

1 <= n <= 2 * 10⁹

Approaches

3 approaches with complexity analysis and trade-offs.

This is a naive approach that directly translates the problem's recurrence relation into a recursive function. The function calculates the minimum days for n by recursively finding the minimum days for the states reachable from n. The key insight is that to use the division operations, we must first have a number of oranges divisible by 2 or 3. We can always reach such a number by eating one orange at a time. This leads to an optimized recurrence which is then implemented without any caching, leading to severe performance issues.

Algorithm

1. Define a recursive function minDays(n).
1. Handle base cases: if n <= 1, return n.
1. Recursively calculate the days required by taking the path towards n/2: (n % 2) + 1 + minDays(n / 2).
1. Recursively calculate the days required by taking the path towards n/3: (n % 3) + 1 + minDays(n / 3).
1. Return the minimum of the two results.

Walkthrough

The core idea is to define a function, say minDays(n), which computes the minimum days to eat n oranges.

The base cases are minDays(0) = 0 and minDays(1) = 1.
For any n > 1, we consider the optimal path. To use the powerful division actions, the number of oranges must be divisible by 2 or 3. The fastest way to get to a multiple of 2 is to eat n % 2 oranges one by one. This takes n % 2 days. Then, one more day is spent on the division action itself. A similar logic applies for division by 3.
This leads to the recurrence: minDays(n) = min( (n % 2) + 1 + minDays(n/2), (n % 3) + 1 + minDays(n/3) ).
A direct implementation of this recurrence without any optimization will lead to re-computation of the same subproblems. For instance, minDays(30) will call minDays(15) and minDays(10). minDays(15) will call minDays(5), and minDays(10) will also call minDays(5). The subproblem for 5 oranges is solved twice. This redundancy grows exponentially.

1public int minDays(int n) {2    if (n <= 1) {3        return n;4    }5    // Option via division by 26    int res1 = (n % 2) + 1 + minDays(n / 2);7    // Option via division by 38    int res2 = (n % 3) + 1 + minDays(n / 3);9    return Math.min(res1, res2);10}

Complexity

Time

Exponential. The function branches into two calls for `n/2` and `n/3`, leading to a large number of redundant computations. This will result in a "Time Limit Exceeded" error for the given constraints.

Space

`O(log n)` due to the maximum depth of the recursion stack.

Trade-offs

Pros

Simple to write and understand the logic.

Cons

Extremely inefficient due to repeated calculations of the same subproblems.
Not feasible for large values of n and will result in a Time Limit Exceeded (TLE) error.

This problem can be viewed as finding the shortest path from a source node n to a target node 0 in a graph. Since each action takes one day, the edges are unweighted, making Breadth-First Search (BFS) a suitable algorithm. We explore the graph level by level, where each level corresponds to an additional day.

Algorithm

1. Initialize a queue and add n.
1. Initialize a visited set and add n.
1. Initialize days = 0.
1. Loop while the queue is not empty:
- a. Process all nodes at the current level.
- b. For each current node dequeued:
  - i. If current is 0, return days.
  - ii. Add its unvisited neighbors (current/3, current/2, current-1) to the queue and visited set.
- c. Increment days.

Walkthrough

We can model the problem as a graph where each integer from 0 to n is a node. From any node k, there are directed edges to k-1, k/2 (if k is even), and k/3 (if k is divisible by 3). We want the shortest path from n to 0. A BFS algorithm explores the graph level by level. We start with a queue containing n. In each step (day), we dequeue all numbers from the queue and enqueue their valid neighbors (k-1, k/2, k/3) that have not been visited yet. We use a HashSet to keep track of visited nodes to avoid cycles and redundant work. The first time we encounter 0, the current number of days is the answer.

1import java.util.HashSet;2import java.util.LinkedList;3import java.util.Queue;4import java.util.Set;5 6class Solution {7    public int minDays(int n) {8        Queue<Integer> queue = new LinkedList<>();9        Set<Integer> visited = new HashSet<>();10        queue.offer(n);11        visited.add(n);12        int days = 0;13        while (!queue.isEmpty()) {14            int levelSize = queue.size();15            for (int i = 0; i < levelSize; i++) {16                int current = queue.poll();17                if (current == 0) {18                    return days;19                }20                if (current % 3 == 0 && !visited.contains(current / 3)) {21                    queue.offer(current / 3);22                    visited.add(current / 3);23                }24                if (current % 2 == 0 && !visited.contains(current / 2)) {25                    queue.offer(current / 2);26                    visited.add(current / 2);27                }28                if (!visited.contains(current - 1)) {29                    queue.offer(current - 1);30                    visited.add(current - 1);31                }32            }33            days++;34        }35        return -1; // Should not be reached36    }37}

Complexity

Time

`O(n)`. In the worst case, the `k-1` transition forces the BFS to explore a large number of states, potentially all integers from `n` down to 0.

Space

`O(n)`. The `visited` set and the queue can grow to hold up to `O(n)` elements in the worst case.

Trade-offs

Pros

A standard and correct algorithm for unweighted shortest path problems.

Cons

The state space is too large for the given constraints, making it impractical.
Will likely cause a Memory Limit Exceeded (MLE) or Time Limit Exceeded (TLE) error.

This is the most efficient approach. It builds upon the optimized recursive formula but avoids re-computation by storing the results of subproblems in a cache (a technique called memoization). Since n can be very large, a HashMap is used for the cache instead of an array. This avoids the exponential complexity of the brute-force approach and the large state space exploration of BFS.

Algorithm

1. Create a HashMap memo to act as a cache.
1. Define a recursive function minDays(n).
1. Base cases: If n <= 1, return n.
1. Memoization check: If n is in memo, return memo.get(n).
1. Recursively compute the two main options:
- a. option1 = (n % 2) + 1 + minDays(n / 2)
- b. option2 = (n % 3) + 1 + minDays(n / 3)
1. Find the minimum of the two options.
1. Store the result in memo before returning it.

Walkthrough

The key insight is that the optimal path to 0 will always prioritize the large reduction steps (division by 2 or 3). To use these steps, the number of oranges must be divisible by 2 or 3. The cost to make n divisible by 2 is n % 2 days (by eating one orange at a time). After that, it takes one more day to perform the division. This gives us the recurrence: minDays(n) = min( (n % 2) + 1 + minDays(n/2), (n % 3) + 1 + minDays(n/3) ). We implement this recurrence with a recursive function. To prevent re-calculating minDays(k) for the same k multiple times, we store the result in a HashMap the first time we compute it. Subsequent calls for the same k will just retrieve the value from the map. This drastically reduces the number of computations because the number of unique subproblems (n, n/2, n/3, n/4, n/6, etc.) is much smaller than n.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    Map<Integer, Integer> memo = new HashMap<>();6    7    public int minDays(int n) {8        if (n <= 1) {9            return n;10        }11        if (memo.containsKey(n)) {12            return memo.get(n);13        }14        15        // Option 1: Path via n/216        int res1 = (n % 2) + 1 + minDays(n / 2);17        18        // Option 2: Path via n/319        int res2 = (n % 3) + 1 + minDays(n / 3);20        21        int result = Math.min(res1, res2);22        memo.put(n, result);23        return result;24    }25}

Complexity

Time

`O((log n)^2)`. The number of states we need to solve for are of the form `n / (2^a * 3^b)`. The number of such distinct states is polylogarithmic with respect to `n`. Each state is computed only once.

Space

`O((log n)^2)`. The space is dominated by the size of the `HashMap` which stores the results for all the distinct states encountered.

Trade-offs

Pros

Highly efficient and passes for large constraints.
Correctly identifies the optimal substructure and avoids redundant work.

Cons

Requires understanding of dynamic programming and memoization.
Uses extra space for the memoization cache.

Solutions

Solution

1class Solution {2private3  Map<Integer, Integer> f = new HashMap<>();4public5  int minDays(int n) { return dfs(n); }6private7  int dfs(int n) {8    if (n < 2) {9      return n;10    }11    if (f.containsKey(n)) {12      return f.get(n);13    }14    int res = 1 + Math.min(n % 2 + dfs(n / 2), n % 3 + dfs(n / 3));15    f.put(n, res);16    return res;17  }18}

1class Solution {2public:3  unordered_map<int, int> f;4  int minDays(int n) { return dfs(n); }5  int dfs(int n) {6    if (n < 2)7      return n;8    if (f.count(n))9      return f[n];10    int res = 1 + min(n % 2 + dfs(n / 2), n % 3 + dfs(n / 3));11    f[n] = res;12    return res;13  }14};

1class Solution:2    def minDays(self, n: int) -> int: @ cache def dfs(n): if n < 2: return n return 1 + min(n % 2 + dfs(n // 2), n % 3 + dfs(n // 3)) return dfs(n)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  Map<Integer, Integer> f = new HashMap<>();4public5  int minDays(int n) { return dfs(n); }6private7  int dfs(int n) {8    if (n < 2) {9      return n;10    }11    if (f.containsKey(n)) {12      return f.get(n);13    }14    int res = 1 + Math.min(n % 2 + dfs(n / 2), n % 3 + dfs(n / 3));15    f.put(n, res);16    return res;17  }18}

1class Solution {2public:3  unordered_map<int, int> f;4  int minDays(int n) { return dfs(n); }5  int dfs(int n) {6    if (n < 2)7      return n;8    if (f.count(n))9      return f[n];10    int res = 1 + min(n % 2 + dfs(n / 2), n % 3 + dfs(n / 3));11    f[n] = res;12    return res;13  }14};

1class Solution:2    def minDays(self, n: int) -> int: @ cache def dfs(n): if n < 2: return n return 1 + min(n % 2 + dfs(n // 2), n % 3 + dfs(n // 3)) return dfs(n)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.