Skip to content

1553. Minimum Number of Days to Eat N Oranges 👍

  • Time: $O(\log^2 n)$
  • Space: $O(\log^2 n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  int minDays(int n) {
    if (n <= 1)
      return n;
    if (const auto it = mem.find(n); it != mem.cend())
      return it->second;
    return mem[n] = 1 + min(minDays(n / 3) + n % 3,  //
                            minDays(n / 2) + n % 2);
  }

 private:
  unordered_map<int, int> mem;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public int minDays(int n) {
    if (n <= 1)
      return n;
    if (dp.containsKey(n))
      return dp.get(n);

    final int res = 1 + Math.min(minDays(n / 3) + n % 3, //
                                 minDays(n / 2) + n % 2);
    dp.put(n, res);
    return res;
  }

  private Map<Integer, Integer> dp = new HashMap<>();
}

1
2
3
4
5
6
7
class Solution:
  @functools.lru_cache(None)
  def minDays(self, n: int) -> int:
    if n <= 1:
      return n
    return 1 + min(self.minDays(n // 3) + n % 3,
                   self.minDays(n // 2) + n % 2)