Minimum number of days to eat n oranges

Dynamic Programming Memoization

36.1% acceptance

Feb 25, 2026

1031

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_days(n: i32) -> i32 {
    let mut memo = std::collections::HashMap::new();
    Self::dfs(n, &mut memo)
  }

  fn dfs(n: i32, memo: &mut std::collections::HashMap<i32, i32>) -> i32 {
    if n <= 1 { return n; }
    if let Some(&v) = memo.get(&n) { return v; }
    // Cost to reach n/2: n%2 steps + 1 day for halving
    let via2 = Self::dfs(n / 2, memo) + n % 2 + 1;
    // Cost to reach n/3: n%3 steps + 1 day for thirding
    let via3 = Self::dfs(n / 3, memo) + n % 3 + 1;
    let res = via2.min(via3);
    memo.insert(n, res);
    res
  }
}