Minimum Number of Days to Eat N Oranges - Problem

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.

Input & Output

Example 1 — Small Number

$ Input: n = 10

› Output: 4

💡 Note: Day 1: eat 1 orange (9 remaining). Day 2: 9%3=0, eat 2*(9/3)=6 oranges (3 remaining). Day 3: 3%3=0, eat 2*(3/3)=2 oranges (1 remaining). Day 4: eat 1 orange (0 remaining). Total: 4 days.

Example 2 — Perfect Division

$ Input: n = 6

› Output: 3

💡 Note: Day 1: 6%2=0, eat 6/2=3 oranges (3 remaining). Day 2: 3%3=0, eat 2*(3/3)=2 oranges (1 remaining). Day 3: eat 1 orange (0 remaining). Total: 3 days.

Example 3 — Base Case

$ Input: n = 1

› Output: 1

💡 Note: Day 1: eat 1 orange (0 remaining). Total: 1 day.

Constraints

1 ≤ n ≤ 2 × 10⁹

Visualization

Tap to expand

Asked in

G Google 45 M Microsoft 32 a Amazon 28 f Facebook 21

The key insight is to focus on reaching numbers divisible by 2 or 3 quickly, then use the efficient batch eating options. The optimal approach uses memoized recursion with smart path selection, achieving O(log n) time complexity by only exploring promising division paths rather than all possible eating sequences.

Common Approaches

✓ Brute Force Recursion

⏱️ Time: O(3ⁿ) Space: O(n)

At each step, recursively try all three eating options (eat 1, eat n/2 if divisible by 2, eat 2*(n/3) if divisible by 3) and return the minimum days needed. This explores all possible paths without any optimization.

Memoization (Top-Down DP)

⏱️ Time: O(n) Space: O(n)

Same recursive approach as brute force, but we store the results of each subproblem in a hash map. When we encounter the same value of n again, we return the cached result instead of recalculating it.

Optimized Memoization (Smart Path Selection)

⏱️ Time: O(log n) Space: O(log n)

Instead of always trying the 'eat 1' option, we first try to reach numbers that are divisible by 2 or 3 by eating individual oranges, then use the efficient batch eating options. This dramatically reduces the search space.

Brute Force Recursion — Algorithm Steps

For each n, try all valid eating options
Recursively solve for remaining oranges
Return minimum days among all choices

Visualization

Tap to expand

Step-by-Step Walkthrough

Start with N=10

Try all three eating options

Branch Out

Each choice creates new subproblems

Exponential Growth

Tree grows exponentially with repeated calculations

Code -

solution.c — C

#include <stdio.h>
#include <limits.h>

int min(int a, int b) {
    return (a < b) ? a : b;
}

int solution(int n) {
    if (n <= 1) {
        return n;
    }
    
    int minDays = INT_MAX;
    
    // Option 1: eat one orange
    minDays = min(minDays, 1 + solution(n - 1));
    
    // Option 2: if divisible by 2, eat n/2 oranges
    if (n % 2 == 0) {
        minDays = min(minDays, 1 + solution(n / 2));
    }
    
    // Option 3: if divisible by 3, eat 2*(n/3) oranges
    if (n % 3 == 0) {
        minDays = min(minDays, 1 + solution(n / 3));
    }
    
    return minDays;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(3ⁿ)

Each call branches into up to 3 recursive calls, creating exponential growth

⚡ Linearithmic

Space Complexity

O(n)

Recursion stack depth can go up to n in worst case

⚡ Linearithmic Space

42.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Minimum Number of Days to Eat N Oranges - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler