# Minimum Number of Days to Eat N Oranges
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-number-of-days-to-eat-n-oranges)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-days-to-eat-n-oranges
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
---
## Problem
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 * 109`

# Approaches
## Brute-Force Recursion
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.
**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.
**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.
### Explanation
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.
```java
public int minDays(int n) {
    if (n <= 1) {
        return n;
    }
    // Option via division by 2
    int res1 = (n % 2) + 1 + minDays(n / 2);
    // Option via division by 3
    int res2 = (n % 3) + 1 + minDays(n / 3);
    return Math.min(res1, res2);
}
```
### Algorithm
- 1. Define a recursive function `minDays(n)`.
- 2. Handle base cases: if `n <= 1`, return `n`.
- 3. Recursively calculate the days required by taking the path towards `n/2`: `(n % 2) + 1 + minDays(n / 2)`.
- 4. Recursively calculate the days required by taking the path towards `n/3`: `(n % 3) + 1 + minDays(n / 3)`.
- 5. Return the minimum of the two results.

## Breadth-First Search (BFS)
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.
**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.
**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.
### Explanation
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.
```java
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution {
    public int minDays(int n) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(n);
        visited.add(n);
        int days = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                int current = queue.poll();
                if (current == 0) {
                    return days;
                }
                if (current % 3 == 0 && !visited.contains(current / 3)) {
                    queue.offer(current / 3);
                    visited.add(current / 3);
                }
                if (current % 2 == 0 && !visited.contains(current / 2)) {
                    queue.offer(current / 2);
                    visited.add(current / 2);
                }
                if (!visited.contains(current - 1)) {
                    queue.offer(current - 1);
                    visited.add(current - 1);
                }
            }
            days++;
        }
        return -1; // Should not be reached
    }
}
```
### Algorithm
- 1. Initialize a queue and add `n`.
- 2. Initialize a `visited` set and add `n`.
- 3. Initialize `days = 0`.
- 4. 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`.

## Top-Down DP with Memoization
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.
**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.
**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.
### Explanation
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`.
```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    Map<Integer, Integer> memo = new HashMap<>();
    
    public int minDays(int n) {
        if (n <= 1) {
            return n;
        }
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        // Option 1: Path via n/2
        int res1 = (n % 2) + 1 + minDays(n / 2);
        
        // Option 2: Path via n/3
        int res2 = (n % 3) + 1 + minDays(n / 3);
        
        int result = Math.min(res1, res2);
        memo.put(n, result);
        return result;
    }
}
```
### Algorithm
- 1. Create a `HashMap` `memo` to act as a cache.
- 2. Define a recursive function `minDays(n)`.
- 3. Base cases: If `n <= 1`, return `n`.
- 4. Memoization check: If `n` is in `memo`, return `memo.get(n)`.
- 5. Recursively compute the two main options:
  - a. `option1 = (n % 2) + 1 + minDays(n / 2)`
  - b. `option2 = (n % 3) + 1 + minDays(n / 3)`
- 6. Find the minimum of the two options.
- 7. Store the result in `memo` before returning it.

# Solutions
### Java

```java
class Solution {
private
  Map<Integer, Integer> f = new HashMap<>();
public
  int minDays(int n) { return dfs(n); }
private
  int dfs(int n) {
    if (n < 2) {
      return n;
    }
    if (f.containsKey(n)) {
      return f.get(n);
    }
    int res = 1 + Math.min(n % 2 + dfs(n / 2), n % 3 + dfs(n / 3));
    f.put(n, res);
    return res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  unordered_map<int, int> f;
  int minDays(int n) { return dfs(n); }
  int dfs(int n) {
    if (n < 2)
      return n;
    if (f.count(n))
      return f[n];
    int res = 1 + min(n % 2 + dfs(n / 2), n % 3 + dfs(n / 3));
    f[n] = res;
    return res;
  }
};

```

### Python

```python
class Solution:
    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)

```