Minimum Number of Days to Eat N Oranges - Practice Coding Problems

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

Understanding the Visualization

Input

n=10 oranges to eat optimally

Strategy

Choose best eating option each day

Output

4 days minimum to eat all oranges

Key Takeaway

🎯 Key Insight: Always aim for numbers divisible by 2 or 3 to use the efficient batch eating options

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

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(3ⁿ)	O(n)	Try all possible eating choices recursively without optimization
Memoization (Top-Down DP)	O(n)	O(n)	Cache recursive results to avoid recalculating same subproblems
Optimized Memoization (Smart Path Selection)	O(log n)	O(log n)	Only explore the most promising paths by focusing on divisibility options

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

✓ Linear Growth

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler