1553. Minimum Number of Days to Eat N Oranges

Description

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 * 10⁹

Solutions

Solution 1: Memoization Search

According to the problem description, for each \(n\), we can choose one of three ways:

Decrease \(n\) by \(1\);
If \(n\) can be divided by \(2\), divide the value of \(n\) by \(2\);
If \(n\) can be divided by \(3\), divide the value of \(n\) by \(3\).

Therefore, the problem is equivalent to finding the minimum number of days to reduce \(n\) to \(0\) through the above three ways.

We design a function \(dfs(n)\), which represents the minimum number of days to reduce \(n\) to \(0\). The execution process of the function \(dfs(n)\) is as follows:

If \(n < 2\), return \(n\);
Otherwise, we can first reduce \(n\) to a multiple of \(2\) by \(n \bmod 2\) operations of \(1\), and then perform operation \(2\) to reduce \(n\) to \(n/2\); we can also first reduce \(n\) to a multiple of \(3\) by \(n \bmod 3\) operations of \(1\), and then perform operation \(3\) to reduce \(n\) to \(n/3\). We choose the minimum of the above two ways, that is, \(1 + \min(n \bmod 2 + dfs(n/2), n \bmod 3 + dfs(n/3))\).

To avoid repeated calculations, we use the method of memoization search and store the calculated values of \(dfs(n)\) in a hash table.

The time complexity is \(O(\log^2 n)\), and the space complexity is \(O(\log^2 n)\).

Python3JavaC++GoTypeScript

class Solution:
    def minDays(self, n: int) -> int:
        @cache
        def dfs(n: int) -> int:
            if n < 2:
                return n
            return 1 + min(n % 2 + dfs(n // 2), n % 3 + dfs(n // 3))

        return dfs(n)

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

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

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

function minDays(n: number): number {
    const f: Record<number, number> = {};
    const dfs = (n: number): number => {
        if (n < 2) {
            return n;
        }
        if (f[n] !== undefined) {
            return f[n];
        }
        f[n] = 1 + Math.min((n % 2) + dfs((n / 2) | 0), (n % 3) + dfs((n / 3) | 0));
        return f[n];
    };
    return dfs(n);
}

1553. Minimum Number of Days to Eat N Oranges

Description

Solutions

Solution 1: Memoization Search

Comments