2749. Minimum Operations to Make the Integer Zero

This is one of those problems where the constraints are a hint: brute force won’t survive. LeetCode itself labels it a real interview question, and it’s the kind of bit-manipulation + math brainteaser that shows up occasionally in big-tech interviews like MAANG, specifically Amazon, Google, and Meta.

Problem statement

Given two integers, num1 and num2, you may repeatedly apply the following operation:

• Choose any integer, i, from 0 to 60 (inclusive).
• Subtract 2i + num2 from the current value of num1.

Return the integer representing the minimum operations needed so that num1 ends up exactly 0. If it cannot be done, return -1.

Constraints:

• 1 <= num1 <= 10⁹
• -10⁹ <= num2 <= 10⁹

Examples

Naive approach: BFS over all possible states

One of the first ideas that comes to mind is to treat the current value of num1 as a state and try to reach 0 in the fewest moves. From a state x, we can choose any i from 0 to 60 and move to x – (2ⁱ + num2). Using BFS, we start from num1, explore all states reachable in 1 move, then 2 moves, and so on. The first time we reach 0, that level gives the minimum number of operations.

While expanding a state, we can generate up to 61 next states (one for each i). We also keep a visited set so we don’t process the same value repeatedly. In theory, this is correct because BFS always explores by increasing the number of moves.

However, this approach won’t work well in practice. The branching factor is 61, so the number of explored states grows extremely fast. Also, num1 can be very large, meaning BFS may have to visit a huge number of different values before it ever reaches 0 (or concludes it’s impossible). Because of this, BFS can take too much time and use too much memory (large queue + visited set), so it is not suitable for the problem constraints.

Key observation

While thinking about BFS, we notice something important: no matter what i values we choose, every move always subtracts num2 once. So, after exactly k operations, we will subtract k × num2 in total, plus some powers of two.

That means after k moves, the total subtracted amount looks like:

k x num2 + (2ⁱ¹ + 2ⁱ² + … + 2^ik)

So, instead of trying all paths like BFS does, we can just try different values of k (number of operations), compute what remains, and check if it is possible. This simple observation is what naturally leads to the optimized solution based on enumerating k rather than exploring all sequences.

Optimized solution: Enumerating k

Instead of trying to find the sequence of operations, we iterate through the number of operations k starting from 1. This works because the final result depends only on the total count of operations, not their specific order.

Mathematical intuition:

After k operations, the total value subtracted from num1 is the sum of k powers of two (2ⁱ¹ + 2ⁱ² + . . . + 2^ik) plus k instances of num2. To find if a specific k is valid, we isolate the powers of two: x = num1 – (k x num2). Here, x represents the value that must be formed by summing exactly k powers of two.

The popcount constraint:

To determine if x can be represented as a sum of exactly k powers of two, we use two bounds:

• The minimum popcount(x): Each 1 in the binary representation of x represents a power of two. Therefore, the minimum number of terms needed to sum to x is the number of set bits (popcount). For example: 13 is 1101 in binary. It requires at least 3 powers: (2³ + 2² + 2⁰).
• The maximum x: The maximum number of powers of two we can use is x itself, by decomposing everything into 2⁰ (i.e., 1 + 1 + 1 . . .). For example: 13 can be written as 13 terms: (1 + 1 + . . . + 1).

What is popcount(x) and why do we use it?

popcount(x) is the number of 1s in the binary form of x. It matters because each 1-bit already forces at least one power of two in the sum, so it gives the minimum number of terms needed. For example, for x = 13, binary is 1101, there are 3 ones, so popcount(13) = 3

Step-by-step algorithm

1. Iterate through values of k from 1 to 60, where k represents the number of operations to try. We stop at 60 because 2⁶⁰ exceeds standard 64-bit integer limits, making further k values mathematically impossible for typical inputs.
2. For each k, compute x = num1 - k * num2 (this is the sum that must be formed using powers of two).
   1. If x <= 0, skip this k because we can’t form a non-positive x using positive powers of two.
   2. Compute the number of 1s in x’s binary form, i.e., the minimum number of powers of two needed, i.e., ones = bit_count(x). Note that we have used Python’s built in function bit_count(x) equivalent to popcount(x).
   3. If ones <= k <= x, then x can be written as a sum of exactly k powers of two, so return k.
3. If no k works, return -1.

Let’s look at the following illustration to better understand the solution.

Python implementation for the optimal solution

Now, look at the Python code that implements the solution approach we discussed above:

def make_the_integer_zero(num1: int, num2: int) -> int:
    # Try k = number of operations (we want the minimum)
    for k in range(1, 61):
        # After k operations, num2 is subtracted k times
        x = num1 - k * num2

        # If x <= 0, we can't represent it as a positive sum of powers of two
        if x <= 0:
            continue

        # Python built-in: int.bit_count() gives popcount (number of 1s in binary)
        ones = x.bit_count()

        # Possible if we can use exactly k terms (min = ones, max = x)
        if ones <= k <= x:
            return k

    # No k worked
    return -1


# Driver code
def main():
    test_cases = [
        (13, 1),     # expected 3
        (7, -1),     # expected 1
        (1, 2),      # expected -1
        (31, 3),     # expected 3
        (100, 7),    # expected 4
    ]

    for idx, (num1, num2) in enumerate(test_cases, 1):
        result = make_the_integer_zero(num1, num2)
        print(f"{idx}.\tnum1 = {num1}, num2 = {num2}")
        print(f"\tOutput: {result}")
        print("-" * 75)


if __name__ == "__main__":
    main()

Time complexity

The time complexity is O(log(num1)) because we test increasing values of k and the key feasibility check relies on properties of x = num1 − k·num2 in binary (via popcount), so the work is tied to the number of bits needed to represent the numbers, which is proportional to log(num1).

Space complexity

The space complexity is O(1) as the algorithm only uses a constant number of variables and no extra data structures.

Common interview mistakes to avoid

This problem looks like a normal minimum operations question, but most mistakes happen when you miss the key binary observation and fall back to brute force.

1. Doing BFS/DFS over num1 values: the branching factor is 61 and the reachable states can explode, causing TLE/memory issues.
2. Using a greedy strategy for choosing i: “subtract the biggest possible” can get stuck even when a valid sequence exists, because feasibility depends on the overall binary form after k moves.
3. Not converting it into a fixed-k check: the crucial step is setting x = num1 - k*num2 and checking if x can be written as a sum of exactly k powers of two.
4. Getting the feasibility condition wrong: the correct test is x > 0 and popcount(x) ≤ k ≤ x; missing k ≤ x or using < instead of ≤ commonly breaks edge cases.
5. Overflow / wrong integer type (C++/Java): k*num2 and shifts like (1LL<<i) need 64-bit types; 32-bit overflow silently causes wrong answers.