Minimum Numbers of Function Calls to Make Target Array: Reverse Engineering with Bits

LeetCode Minimum Numbers of Function Calls to Make Target Array (Problem 1558) asks: given a target array of non-negative integers, find the minimum number of function calls to transform an array of all zeros into the target. You have two operations: pick an index and add 1 to that element, or multiply every element by 2.

At first glance, this looks like it needs BFS or dynamic programming. But if you think about it backwards, from the target to the zeros, a clean greedy pattern emerges.

Why this problem matters

This problem sits at the intersection of greedy algorithms and bit manipulation. It teaches you to reverse-engineer a construction process by analyzing the binary structure of the target values. The same "work backwards" technique applies to a whole family of problems where you are building something from scratch with a limited set of operations.

It also reinforces a practical skill: recognizing when a global operation (multiply all by 2) and a local operation (add 1 to one element) can be analyzed separately instead of simulated step by step.

The key insight

Work backwards from the target. Instead of figuring out the forward sequence of operations, ask: what was the last operation that produced each number?

If a number is odd, the last operation on it must have been "add 1" (since multiplying by 2 always produces an even number). If a number is even, it could have been produced by "multiply all by 2."

This maps directly to binary representations:

• The number of 1-bits (set bits) in a number tells you how many add-1 operations that element needed. Each set bit represents a point where you had to increment before a subsequent doubling.
• The bit length minus 1 tells you how many multiply-by-2 operations were needed to shift the highest bit into position.

The multiply-by-2 operation is shared across all elements (it doubles everything at once), so you only need enough doublings for the element with the longest binary representation. The add-1 operations are per-element, so you sum them across all numbers.

The formula: total = sum of set bits across all numbers + max(bit_length - 1, 0).

The solution

def min_operations(nums: list[int]) -> int:
    add_ops = 0
    max_bits = 0
    for num in nums:
        bits = 0
        while num > 0:
            add_ops += num & 1
            num >>= 1
            bits += 1
        max_bits = max(max_bits, bits)
    return add_ops + max(0, max_bits - 1)

Here is what each piece does:

1. add_ops accumulates the total number of set bits across all numbers. For each number, num & 1 checks the lowest bit. If it is 1, we need one add-1 operation for that bit position. Then num >>= 1 shifts right to examine the next bit.
2. bits counts the total number of bit positions (the bit length) for the current number. After processing all bits, max_bits tracks the longest binary representation seen so far.
3. max(0, max_bits - 1) gives the number of multiply-by-2 operations. A number with k bits needs k - 1 doublings. We take the max because doublings are shared across all elements. The max(0, ...) handles the edge case where all numbers are 0 (bit length 0).

Visual walkthrough

Let's trace through the example nums = [1, 5]. The expected answer is 5.

Working backwards confirms this: start with [1, 5]. Since 5 is odd, subtract 1 to get [1, 4]. Now 4 is even and 1 is odd, so subtract 1 from index 0 to get [0, 4]. Divide all even values by 2: [0, 2]. Divide by 2 again: [0, 1]. Subtract 1: [0, 0]. That is 3 subtract-1 steps and 2 divide-by-2 steps, totaling 5.

Complexity analysis

Here n is the length of the array and m is the maximum value in the array. For each element, we process at most log m bits. The space is constant because we only track two running totals.

The building blocks

1. Counting set bits

The core technique of iterating through a number's bits using num & 1 and num >>= 1 is a fundamental bit manipulation pattern. You use it any time you need to analyze the binary structure of a number, whether counting 1-bits, extracting specific bit positions, or computing parity.

count = 0
while num > 0:
    count += num & 1
    num >>= 1

This same loop appears in Number of 1 Bits, Hamming Distance, and dozens of other problems. Once you can write it from memory, you have a reusable tool for any problem involving binary decomposition.

2. Working backwards (reverse simulation)

Instead of simulating the forward process (which has a huge search space), you reverse the operations. "Add 1" becomes "subtract 1," and "multiply all by 2" becomes "divide all by 2." The reverse direction is deterministic: odd numbers must have had 1 subtracted, and even numbers can be halved.

This reverse-simulation pattern shows up in problems like Broken Calculator, where you work from the target back to the start because the reverse operations are simpler to reason about.

Edge cases

• All zeros. If every element is 0, no operations are needed. The loop produces add_ops = 0 and max_bits = 0, so the result is 0 + max(0, -1) = 0.
• Single element of 1. nums = [1]: one set bit, bit length 1. Result = 1 + max(0, 0) = 1. Just one add-1 operation.
• All elements are the same power of 2. For example, nums = [4, 4, 4]. Each 4 = 100 in binary has 1 set bit and 3-bit length. Result = 3 + 2 = 5. Three add-1 ops and two doublings.
• Mix of zeros and non-zeros. Zeros contribute nothing to add_ops or max_bits. They are free since doubling 0 stays 0 and you never need to increment them.
• Large values. Values up to 10^9 have at most 30 bits. The algorithm handles them efficiently since it processes each bit once.
• Single element with large value. nums = [1000000000]: 30 bits, 15 set bits. Result = 15 + 29 = 44.

From understanding to recall

The insight here is clean: set bits count individual increments, max bit length counts shared doublings. But translating that into working code under time pressure requires practice. You need to remember the num & 1 / num >>= 1 loop, the separate tracking of add_ops and max_bits, and the max(0, max_bits - 1) formula.

Spaced repetition builds that recall. You write the solution from scratch today, again in three days, then a week later. Each repetition strengthens the connection between "minimum operations to build an array" and "count set bits plus max bit length." Eventually, you see the problem statement and the solution structure is already in your head before you start typing.

Related posts

• Divide Two Integers - Another problem that uses bit shifting for efficient arithmetic operations
• Number of 1 Bits - Direct practice with the set-bit counting technique used here
• Single Number - Fundamental bit manipulation pattern with XOR

CodeBricks breaks the minimum function calls problem into its bit-counting and reverse-simulation building blocks, then drills them independently with spaced repetition. You type the set-bit loop from scratch until it is automatic. When a bit manipulation question shows up in your interview, you do not hesitate. You just write it.