Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1553.html

1553. Minimum Number of Days to Eat N Oranges (Hard)

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.

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.

Example 3:

Input: n = 1
Output: 1

Example 4:

Input: n = 56
Output: 6

 

Constraints:

  • 1 <= n <= 2*10^9

Related Topics:
Dynamic Programming

Solution 1. DP

The idea of the solution is not hard – basically use DFS to try n-1, n/2, n/3 cases and memoize the minimal value.

One caveat is that we shouldn’t do n-1 case every time because that will regress our solution to O(N) time complexity.

In fact, we should eat n % 2 oranges one-by-one and then swallow n / 2, or eat n % 3 oranges so that we can gobble 2 * n / 3.

We need to prove that this works. This solution can be expressed as “we should never take more than 2 consecutive -1 operations”.

We can prove by contradiction:

Assume there exits some n that we need to take 3 consecutive -1 operations for optimal solution, i.e. minDays(n) = minDays(n - 3) + 3.

If the first operation we take for n - 3 is /2, then n is odd. Since (n - 3) / 2 = (n - 1) / 2 - 1, we can see that taking -1, /2, -1 3 operations is better than taking -1, -1, -1, /2 4 operations. So taking 3 -1 operations is not optimal in this case.

If the first operation we take for n - 3 is /3, so n is divisible by 3. Since (n - 3) / 3 = n / 3 - 1, we can see that taking /3, -1 2 operations is better than taking -1, -1, -1, /3 4 operations. So taking 3 -1 operations is not optimal in this case.

This process can be extended to taking k >= 3 consecutive -1s.

Thus the conclusion is taht we should always at most take 2 consecutive -1 operations.

// OJ: https://leetcode.com/problems/minimum-number-of-days-to-eat-n-oranges/
// Time: O(logN)
// Space: O(logN)
class Solution {
    unordered_map<int, int> m;
public:
    int minDays(int n) {
        if (n <= 1) return n;
        if (m.count(n)) return m[n];
        return m[n] = 1 + min(minDays(n / 3) + n % 3, minDays(n / 2) + n % 2);
    }
};

  • class Solution {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();

    public int minDays(int n) {
        if (n <= 1)
            return n;
        if (map.containsKey(n))
            return map.get(n);
        int days = Math.min(minDays(n / 2) + n % 2 + 1, minDays(n / 3) + n % 3 + 1);
        map.put(n, days);
        return days;
    }
}

############

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;
    }
}

  • // OJ: https://leetcode.com/problems/minimum-number-of-days-to-eat-n-oranges/
// Time: O(logN)
// Space: O(logN)
class Solution {
    unordered_map<int, int> m;
public:
    int minDays(int n) {
        if (n <= 1) return n;
        if (m.count(n)) return m[n];
        return m[n] = 1 + min(minDays(n / 3) + n % 3, minDays(n / 2) + n % 2);
    }
};

  • 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)



  • func minDays(n int) int {
	f := map[int]int{0: 0, 1: 1}
	var dfs func(int) int
	dfs = func(n int) int {
		if v, ok := f[n]; ok {
			return v
		}
		res := 1 + min(n%2+dfs(n/2), n%3+dfs(n/3))
		f[n] = res
		return res
	}
	return dfs(n)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

All Problems

All Solutions