Minimum Number of Days to Eat N Oranges Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5
6
7

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.

Solution

Method 1 – Memoized DFS

Intuition

We want the minimum number of days to eat all oranges, and each day we can eat 1, n/2, or 2*(n/3) oranges if possible. Since the same subproblem can be reached by different paths, memoization helps avoid redundant calculations.

Approach

  1. Use a recursive function with memoization to store results for each n.
  2. For each n, try:
    • Eating 1 orange (n-1).
    • If n divisible by 2, eat n/2 oranges (n//2).
    • If n divisible by 3, eat 2*(n/3) oranges (n//3).
  3. For divisibility, also consider the cost to reach a divisible state (eat 1 orange until divisible).
  4. Return the minimum days among all options.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

func minDays(n int) int {
    memo := map[int]int{}
    var dfs func(int) int
    dfs = func(x int) int {
        if x <= 1 {
            return x
        }
        if v, ok := memo[x]; ok {
            return v
        }
        ans := 1 + min(x%2+dfs(x/2), x%3+dfs(x/3))
        memo[x] = ans
        return ans
    }
    return dfs(n)
}
func min(a, b int) int { if a < b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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);
        int ans = 1 + Math.min(
            n % 2 + minDays(n / 2),
            n % 3 + minDays(n / 3)
        );
        memo.put(n, ans);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    val memo = mutableMapOf<Int, Int>()
    fun minDays(n: Int): Int {
        if (n <= 1) return n
        memo[n]?.let { return it }
        val ans = 1 + minOf(
            n % 2 + minDays(n / 2),
            n % 3 + minDays(n / 3)
        )
        memo[n] = ans
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def minDays(n: int) -> int:
    memo: dict[int, int] = {}
    def dfs(x: int) -> int:
        if x <= 1:
            return x
        if x in memo:
            return memo[x]
        ans = 1 + min(x % 2 + dfs(x // 2), x % 3 + dfs(x // 3))
        memo[x] = ans
        return ans
    return dfs(n)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

use std::collections::HashMap;
impl Solution {
    pub fn min_days(n: i32) -> i32 {
        fn dfs(x: i32, memo: &mut HashMap<i32, i32>) -> i32 {
            if x <= 1 { return x; }
            if let Some(&v) = memo.get(&x) { return v; }
            let ans = 1 + (x % 2 + dfs(x / 2, memo)).min(x % 3 + dfs(x / 3, memo));
            memo.insert(x, ans);
            ans
        }
        let mut memo = HashMap::new();
        dfs(n, &mut memo)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    memo = new Map<number, number>();
    minDays(n: number): number {
        if (n <= 1) return n;
        if (this.memo.has(n)) return this.memo.get(n)!;
        const ans = 1 + Math.min(
            n % 2 + this.minDays(Math.floor(n / 2)),
            n % 3 + this.minDays(Math.floor(n / 3))
        );
        this.memo.set(n, ans);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(log n), since each recursive call reduces n by at least half or a third, and memoization avoids recomputation.
  • 🧺 Space complexity: O(log n), for the recursion stack and memoization.