Python 1558.py
class Solution:
def minOperations(self, nums: List[int]) -> int:
bits = [ 0 ] * 32
for n in nums:
for i in range(32):
if n < (1 << i): # just a performance optimization
break
if n & (1 << i):
bits[i] += 1
# eliminate unused bits
while bits and bits[-1] == 0:
bits.pop()
# all zeros
if not bits:
return 0
return sum(bits) + len(bits) - 1 # sum => add/op=0, len => shift/op=1
Difficulty
and has an acceptance rate of about 63% (40k+ submissions).
Typical patterns to solve this problem:
- Array
- Bit Manipulation
- Greedy
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 computes the minimum number of operations required to reduce a list of non-negative integers to zero using two allowed operations: adding one to a number and left-shifting all numbers (equivalent to multiplying by two). The algorithm works by analyzing the binary representation of each integer, counting how many times each bit position is set across the entire list, and then deriving the operation count from those aggregates.
Counting Set Bits
The first major step creates a fixed-size array to hold the count of set bits for each of the 32 possible positions in a 32-bit integer. The code iterates over every number and, for each bit position, checks whether the current number has that bit set. When a number is smaller than the current power of two, the inner loop terminates early, avoiding unnecessary checks for higher bit positions.
bits = [0] * 32
for n in nums:
for i in range(32):
if n < (1 << i): # early exit when higher bits cannot be set
break
if n & (1 << i):
bits[i] += 1
The early exit condition (n < (1 << i)) is a deliberate performance optimization. It prevents the algorithm from iterating through all 32 bit positions for numbers that have a small magnitude, reducing the total number of bitwise operations.
Trimming Unused Bit Positions
After counting, the algorithm removes trailing entries in the bits array that remain zero. This step eliminates bit positions that never appear in any number, ensuring that subsequent calculations only consider relevant bits.
while bits and bits[-1] == 0:
bits.pop()
The loop continues until the last element of the list is non-zero or the list becomes empty. This handling gracefully covers the case where every number in the input is zero, resulting in an empty bits list.
Handling the All-Zero Edge Case
When the input consists solely of zeros, the bits list is emptied by the trimming loop. The method detects this situation and returns zero immediately, indicating that no operations are needed.
if not bits:
return 0
This explicit check ensures that the function does not attempt further calculations on an empty list, which would otherwise lead to incorrect results.
Final Operation Count
The remaining non-zero entries in bits represent the distribution of set bits across the numbers. The total number of “add one” operations equals the sum of all counts, because each set bit must be introduced by an addition at some point. The number of “shift” operations corresponds to the number of distinct bit positions that are used, which is the length of the trimmed bits list minus one (the first position does not require a preceding shift). The method combines these two contributions into a single expression.
return sum(bits) + len(bits) - 1
The comment clarifies the mapping: sum(bits) accounts for addition operations, while len(bits) - 1 accounts for shift operations.
Edge Cases Addressed
The algorithm correctly handles inputs where:
- All numbers are zero, returning zero operations.
- The list contains a single element, whether zero or non-zero, by counting its bits and applying the same formula.
- Numbers have varying magnitudes, thanks to the early break in the inner loop that stops scanning once the current power of two exceeds the number.
Performance Optimizations Observed
Two notable optimizations are present:
- Preallocation of a fixed-size list (
bits = [0] * 32) avoids dynamic resizing during counting. - The early termination condition inside the inner loop (
if n < (1 << i): break) reduces the number of bitwise checks for small numbers, which can be significant when the input contains many low-value integers.
Together, these choices keep the inner processing tight and avoid unnecessary work, especially for inputs dominated by small values.
ELI5 - Simplified Explanation
Imagine you have a big collection of colorful building blocks that represent the numbers in the list. Each number is made up of a secret code that computers use, which is just a bunch of zeros and ones stacked together in a line.
The code starts by creating a row of thirty-two empty buckets to hold these pieces. It looks at every number in the list one by one and peels off each piece of the code to see if it is a one or a zero. If the piece is a one, it drops it into the matching bucket. This way, all the ones are sorted into their own piles based on where they belong in the code.
Once all the numbers are sorted, it looks at the very end of the row. If any of the buckets in the back are completely empty, it tosses them away because they are not needed.
Finally, it calculates the answer by looking at the remaining buckets. It adds up all the pieces sitting inside those buckets and adds the number of buckets left over to find out how many steps are needed to make all the numbers match.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
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 | ||||
| Progiez | C++ | Python | Java | |||||
| github | black-shadows | C++ | ||||||
| charles-wangkai | Java | |||||||
| FelixFan1122 | Java | |||||||
| fsq | C++ | |||||||
| JoshCrozier | JS | |||||||
| keineahnung2345 | C++ | |||||||
| lkwq007 | Python | |||||||
| suxrobGM | C# | |||||||
| trung-hn | Python | |||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||
| WalkCCC | C++, Python, Java | |||||||
| leetcode.ca | C++, Go, Java, Python | |||||||
| Progiez | C++, Java, Python | |||||||
| black-shadows | C++, C++ | |||||||
| charles-wangkai | Java | |||||||
| FelixFan1122 | Java | |||||||
| fsq | C++ | |||||||
| JoshCrozier | JavaScript | |||||||
| keineahnung2345 | C++ | |||||||
| lkwq007 | Python | |||||||
| suxrobGM | C# | |||||||
| trung-hn | Python |
Videos
Solved On The Same Day
- problem 1331: Rank Transform of an Array
- problem 1332: Remove Palindromic Subsequences
- problem 1475: Final Prices With a Special Discount in a Shop
- problem 424: Longest Repeating Character Replacement
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