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
Difficulty
and has an acceptance rate of about 36% (100k+ submissions).
Typical patterns to solve this problem:
- Dynamic Programming
- Memoization
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
Other Solutions
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++ |
Videos
Solved On The Same Day
- problem 464: Can I Win
- problem 729: My Calendar I
- problem 1286: Iterator for Combination
- problem 1348: Tweet Counts Per Frequency
- problem 1387: Sort Integers by The Power Value
- problem 2424: Longest Uploaded Prefix
- problem 327: Count of Range Sum
- problem 699: Falling Squares
- problem 1611: Minimum One Bit Operations to Make Integers Zero
Extra
- 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