Practice/Google/Leetcode 1553. Minimum Number of Days to Eat N Oranges

Leetcode 1553. Minimum Number of Days to Eat N Oranges

CodingMust

Problem

You have n pieces of fruit in your basket. Each day, you must eat some fruit according to the following rules:

• Option 1: Eat exactly 1 piece of fruit
• Option 2: If the current number is divisible by 2, you may eat half of all the fruit (leaving n/2 pieces)
• Option 3: If the current number is divisible by 3, you may eat two-thirds of all the fruit (leaving n/3 pieces)

Your goal is to eat all the fruit (reduce the count to zero) in the minimum number of days.

Return the minimum number of days needed to eat all n pieces of fruit.

Requirements

1. Implement a function that computes the minimum number of days
2. Handle very large values of n efficiently (up to 2 × 10^9)
3. Consider all three eating options optimally at each step
4. The solution must run in reasonable time despite the large constraint

Constraints

• 1 ≤ n ≤ 2 × 10^9
• The answer will fit in a 32-bit integer
• A naive linear dynamic programming approach will be too slow
• Expected time complexity: O(log²n) with memoization
• Expected space complexity: O(log n) for the recursion stack and cache

Examples

Example 1:

Input: n = 10 Output: 4 Explanation: Day 1: Eat 1 fruit (9 remaining) Day 2: 9 is divisible by 3, eat 6 fruit leaving 3 Day 3: 3 is divisible by 3, eat 2 fruit leaving 1 Day 4: Eat 1 fruit (0 remaining) Total: 4 days

Example 2:

Input: n = 6 Output: 3 Explanation: Day 1: 6 is divisible by 2, eat 3 fruit leaving 3 Day 2: 3 is divisible by 3, eat 2 fruit leaving 1 Day 3: Eat 1 fruit (0 remaining) Total: 3 days

Example 3:

Input: n = 1 Output: 1 Explanation: Day 1: Eat 1 fruit (0 remaining) Total: 1 day

Example 4:

Input: n = 82 Output: 7 Explanation: One optimal path: 82 → 81 (eat 1) → 27 (÷3) → 26 (eat 1) → 13 (÷2) → 12 (eat 1) → 4 (÷3) → 2 (÷2) → 0 This takes 7 days total.