Problem 1553

Abstract / Summary

Given n oranges where you can eat one or double the previously eaten amount each day find the fewest days to eat all oranges.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1553.py

class Solution:
    def minDays(self, n: int) -> int:
        dp  = set([n])
        day = 0
        while True:
            next = set()
            for x in dp:
                # last day: always eat one orange
                if x == 1:
                    return day + 1

                next.add(x - 1) # strategy A: eat one

                # strategy B: eat half
                if x % 2 == 0:
                    next.add(x // 2)

                # strategy C: eat two thirds
                if x % 3 == 0:
                    next.add(x // 3)

            dp = next
            day += 1
23 lines | 619 bytes | submitted September 29, 2023 | GitHub   25% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 36% (100k+ submissions).

Typical patterns to solve this problem:
  • Dynamic Programming
  • Memoization
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a method that determines the smallest number of days required to reduce a given integer n to zero by repeatedly applying three possible actions: subtract one, halve the value when it is even, or reduce it to a third when it is divisible by three. The algorithm explores all reachable values day by day until the terminal condition is met.

Key Steps

The computation begins by placing the initial value n into a collection that represents the set of states reachable on the current day.

dp  = set([n])
day = 0

A loop runs indefinitely, generating the set of states that can be reached on the next day.

while True:
    next = set()
    for x in dp:
        ...
    dp = next
    day += 1

Inside the inner loop each state x is examined. When x equals 1 the algorithm knows that one more day of eating a single orange will finish the process, so it returns the total days counted so far plus one.

if x == 1:
    return day + 1

If the state is not the terminal one, the algorithm adds the result of the three possible actions to the collection for the next day. The first action always subtracts one.

next.add(x - 1)   # strategy A: eat one

When the current value is even, halving it is a valid move and the resulting state is added.

if x % 2 == 0:
    next.add(x // 2)

Similarly, when the value is a multiple of three, reducing it to a third is also considered.

if x % 3 == 0:
    next.add(x // 3)

After all current states have been processed, the set dp is replaced by next, and the day counter is incremented, moving the search forward one step in time.

Edge Cases Handled

The algorithm explicitly checks for the situation where the current value is exactly 1. In that case it knows that the optimal solution is to spend a single additional day, avoiding any further expansion of states. This handles the smallest possible input without entering the general expansion logic.

Divisibility checks for two and three ensure that the halving and one-third operations are only applied when mathematically valid. Consequently, values that are not multiples of these numbers are automatically reduced by the “eat one” action, guaranteeing progress toward termination for any positive integer input.

Because the state set is a Python set, duplicate values generated by different paths are automatically merged, preventing redundant processing of identical states that could otherwise arise from multiple sequences of actions leading to the same number.

Performance Optimizations

Using a set for the current frontier provides two important efficiencies. First, it eliminates duplicate entries that would otherwise cause the inner loop to revisit the same value multiple times within a single day, reducing the number of iterations required. Second, the constant-time membership checks and insertions of a hash-based set keep the expansion step fast even as the number of reachable values grows.

The breadth-first search nature of the loop guarantees that the first time the terminal condition (x == 1) is encountered corresponds to the minimal number of days, allowing the method to stop immediately without exploring deeper levels. This early exit prevents unnecessary work once the optimal solution is found.

Incrementally building the next day's state set rather than modifying the current set in place preserves the integrity of the level-by-level exploration, ensuring that each day’s expansion is based solely on states reachable at the start of that day. This disciplined separation of layers contributes to predictable performance characteristics throughout the execution.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a giant basket filled with oranges and a very hungry monster who wants to finish them all. This code is like a game where the monster tries to find the quickest way to empty the basket. The monster has three secret moves to make. The first move is to eat just one single orange. The second move is to eat half of the oranges at once, but only if the number of oranges can be split perfectly into two equal piles. The third move is to eat two thirds of the oranges, which means leaving only one third behind, but this only works if the number of oranges can be shared fairly among three people.

The code starts by keeping track of how many oranges are in the basket on the very first day. Since the monster wants to finish as fast as possible, it looks at all the different ways the basket could look after one day of munching. It keeps repeating this process over and over, checking every possibility for the next day. It keeps a count of how many days have passed while it searches. Eventually, it discovers the exact moment when the basket is finally empty. Every step represents a new day, and the code keeps exploring every choice until it finds the fastest path to zero.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 5.85 | σ = 1.90

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Go TS
Progiez C++ Python Java
github black-shadows C++
charles-wangkai Java
everthis JS
fsq C++
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
suxrobGM C#
wisdompeak C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, TypeScript
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
everthis JavaScript
fsq C++
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
suxrobGM C#
wisdompeak C++
24 links | 13 authors | 7 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

6 medium 3 hard
10 solutions   September 29, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality