Om Shree

Posted on Sep 5

🎿“Minimum Operations to Make the Integer Zero” LeetCode: 2749 [C++, JavaScript, Python]

#programming #cpp #javascript #python

Competitive programming problems often look strange at first. Some of them feel like puzzles written just to confuse us, but after digging deeper, they usually reveal an elegant pattern. LeetCode Problem 2749, Minimum Operations to Make the Integer Zero, is a great example.

The problem asks us to take a number, perform repeated operations, and reduce it to exactly zero. The rules look unusual: in each step we subtract a value of the form (2^i + num2) where i can be any number from 0 to 60. The task is to find the minimum number of operations needed, or decide that it is impossible.

This article explains the problem in plain English, step by step. We will walk through the core idea, understand the logic behind the solution, and finally look at clean code examples in C++, Python, and JavaScript.

Problem Restatement

We are given two integers: num1 and num2.

In one operation, we may choose any integer i between 0 and 60.
We subtract (2^i + num2) from num1.
Our goal is to make num1 equal to zero.
If it is possible, we return the smallest number of operations required.
If it is not possible, we return -1.

Example 1

Input: num1 = 3, num2 = -2
Output: 3

Explanation:

First operation: choose i = 2. Subtract (4 + -2) = 2. Now num1 becomes 1.
Second operation: again i = 2. Subtract 2 again. Now num1 becomes -1.
Third operation: choose i = 0. Subtract (1 + -2) = -1. Now num1 becomes 0.

It took exactly 3 steps.

Example 2

Input: num1 = 5, num2 = 7
Output: -1

Explanation: No sequence of operations will make num1 equal to zero in this case.

Key Observations

The main challenge is understanding what happens when we repeat operations. Let’s think carefully.

After performing k operations, we will have subtracted:

(2^i1 + num2) + (2^i2 + num2) + ... + (2^ik + num2)

That equals:

(sum of k powers of two) + (k * num2)

So, after k operations:

num1 - (sum of k powers of two) - (k * num2) = 0

Rearranging:

num1 - k * num2 = sum of k powers of two

Let’s call this value T:

T = num1 - k * num2

Now the question becomes: can we express T as the sum of exactly k powers of two?

This leads to three simple rules:

T must be positive
Because the sum of positive powers of two cannot be zero or negative.
The number of terms matters
The minimum number of powers of two needed to form a number is the number of 1s in its binary representation. For example, 13 in binary is 1101. It has three set bits, so the smallest way to form 13 is 8 + 4 + 1.
This count is called the popcount. So we need:
popcount(T) <= k
Upper bound condition
The smallest sum of k powers of two is just k (using 1 + 1 + ...). So we must also have:
k <= T

So the conditions are:

T > 0
popcount(T) <= k <= T

Approach

Now that we know the rules, the solution is straightforward.

Loop over all possible values of k from 1 to 60.
(Why 60? Because i is only allowed up to 60, and 2^60 is already much larger than num1’s limits.)
For each k:

Calculate T = num1 - k * num2.
If T is not positive, skip it.
If popcount(T) <= k <= T, then k is valid. Return k immediately.

If we finish the loop without finding any valid k, return -1.

This runs very fast because it only checks up to 60 values.

Example Walkthroughs

Example A

num1 = 3, num2 = -2

Try k = 1: T = 3 - (1 * -2) = 5. popcount(5) = 2. But 2 > 1, so not valid.
Try k = 2: T = 3 - (2 * -2) = 7. popcount(7) = 3. But 3 > 2, not valid.
Try k = 3: T = 3 - (3 * -2) = 9. popcount(9) = 2. 2 <= 3 <= 9, valid! Answer = 3.

Example B

num1 = 5, num2 = 7

k = 1: T = 5 - 7 = -2. Invalid.
k = 2: T = 5 - 14 = -9. Invalid.
Larger k will only make T smaller (more negative). So no solution. Answer = -1.

Implementations

C++ Solution

class Solution {
public:
    int makeTheIntegerZero(long long num1, long long num2) {
        for (long long k = 1; k <= 60; ++k) {
            long long T = num1 - k * num2;
            if (T <= 0) continue;
            if (__builtin_popcountll(T) <= k && k <= T) {
                return (int)k;
            }
        }
        return -1;
    }
};

Python Solution

class Solution:
    def makeTheIntegerZero(self, num1: int, num2: int) -> int:
        for k in range(1, 61):
            T = num1 - k * num2
            if T <= 0:
                continue
            if T.bit_count() <= k <= T:
                return k
        return -1

JavaScript Solution

var makeTheIntegerZero = function(num1, num2) {
  const N1 = BigInt(num1), N2 = BigInt(num2);

  const popcount = (x) => {
    let c = 0n;
    while (x > 0n) {
      x &= (x - 1n);
      c++;
    }
    return c;
  };

  for (let k = 1n; k <= 60n; k++) {
    const T = N1 - k * N2;
    if (T <= 0n) continue;
    if (popcount(T) <= k && k <= T) return Number(k);
  }
  return -1;
};

Why This Works

The solution is based on how binary numbers behave. Every positive integer has a unique binary form, and the number of 1s in that form tells us the smallest number of powers of two needed. If we want more terms, we can break large powers into smaller ones. But if we want fewer terms than the popcount, it is impossible.

By looping over possible operation counts and checking the simple conditions, we quickly find the answer or conclude it is impossible.

Conclusion

This problem is a nice blend of binary math and careful reasoning. At first, the operation (2^i + num2) feels awkward, but when broken down, it becomes clear that the main task is deciding if a number can be represented as the sum of exactly k powers of two.

The important insights are: