Problem 1558

Abstract / Summary

Find the fewest steps to build a target array by copying or adding values using allowed operations.

Note

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

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
19 lines | 564 bytes | submitted January 12, 2024 | GitHub   28% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 63% (40k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Bit Manipulation
  • Greedy
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 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.

written by openai gpt

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.

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 | μ = 6.89 | σ = 1.47

Complexity Analysis

Time: linear
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
generated automatically

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
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
23 links | 13 authors | 7 languages

Videos

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

Solved On The Same Day

5 solutions   January 12, 2024

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