# Minimum Operations to Make the Integer Zero
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-operations-to-make-the-integer-zero)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-the-integer-zero
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
---
## Problem
You are given two integers `num1` and `num2`.

In one operation, you can choose integer `i` in the range `[0, 60]` and subtract `2i + num2` from `num1`.

Return _the integer denoting the **minimum** number of operations needed to make_ `num1` _equal to_ `0`.

If it is impossible to make `num1` equal to `0`, return `-1`.

**Example 1:**

**Input:** num1 = 3, num2 = -2
**Output:** 3
**Explanation:** We can make 3 equal to 0 with the following operations:
- We choose i = 2 and subtract 22 + (-2) from 3, 3 - (4 + (-2)) = 1.
- We choose i = 2 and subtract 22 + (-2) from 1, 1 - (4 + (-2)) = -1.
- We choose i = 0 and subtract 20 + (-2) from -1, (-1) - (1 + (-2)) = 0.
It can be proven, that 3 is the minimum number of operations that we need to perform.

**Example 2:**

**Input:** num1 = 5, num2 = 7
**Output:** -1
**Explanation:** It can be proven, that it is impossible to make 5 equal to 0 with the given operation.

**Constraints:**

* `1 <= num1 <= 109`
* `-109 <= num2 <= 109`

# Approaches
## Efficient Iterative Search
The problem requires finding the minimum number of operations to make `num1` zero. An operation consists of subtracting `2^i + num2`. If we perform `k` operations, the total subtracted amount is the sum of `k` terms of the form `2^i + num2`.

This leads to the equation: `num1 - k * num2 = sum of k powers of 2`.

Let's define `target = num1 - k * num2`. The problem is equivalent to finding the smallest positive integer `k` such that `target` can be represented as a sum of `k` powers of 2. A positive integer `T` can be represented as a sum of `k` powers of 2 if and only if two conditions are met:
1.  The number of set bits in `T`'s binary representation (its population count) is at most `k`. (`Long.bitCount(T) <= k`)
2.  `T` itself is at least `k`. (`T >= k`)

With this insight, we can devise an efficient algorithm by iterating through `k = 1, 2, 3, ...` and for each `k`, calculating the corresponding `target` and checking if it satisfies the two conditions. The first `k` that does is our minimal answer.
**Time:** O(1) - The loop runs for a small constant number of iterations (e.g., up to 60). Inside the loop, operations like subtraction, multiplication, and bit counting take constant time for 64-bit integers. Therefore, the total time complexity is constant. · **Space:** O(1) - The algorithm uses a constant amount of extra space, regardless of the input size.
**Pros:** The approach is simple to understand and implement.; It is very efficient, as it involves a loop with a small, constant number of iterations.; It correctly handles all edge cases based on the problem constraints.
**Cons:** The logic relies on the observation that the required number of operations `k` is small, which holds true for the given constraints but might not be immediately obvious without analysis.
### Explanation
The core of this approach is to iterate through the number of operations, `k`, starting from 1, and for each `k`, check if a solution is possible. 

For a given `k`, we calculate `target = num1 - k * num2`. For this `k` to be a valid number of operations, `target` must be representable as a sum of `k` powers of 2. The conditions for this are:
*   `target >= k`: The smallest sum of `k` powers of 2 is `k` (by choosing `2^0` for all `k` terms).
*   `Long.bitCount(target) <= k`: The minimum number of powers of 2 that can sum to `target` is its population count (the number of set bits in its binary form).

We can loop `k` from 1 upwards. In each iteration, we compute `target` and check if `target >= k` and `Long.bitCount(target) <= k`. The first `k` for which both are true is the minimum number of operations.

An important optimization is to realize that if `num1 < num2`, no solution exists. This is because `num2` must be positive (since `num1 >= 1`), and `target` for `k=1` would be `num1 - num2 < 0`. For larger `k`, `target` would be even more negative. A negative number cannot be a sum of powers of 2.

The loop for `k` does not need to run indefinitely. The constraints on `num1` and the nature of `Long.bitCount` imply that `k` will not be very large. The number of bits in `target` for the relevant `k` values is bounded (around 36-40 bits), so its `bitCount` is also bounded. The condition `k >= Long.bitCount(target)` will be met for a relatively small `k`. A loop up to a safe constant like 60 is sufficient.

```java
class Solution {
    public int makeTheIntegerZero(int num1, int num2) {
        // If num1 < num2, it's impossible. For k=1, num1 - num2 < 0.
        // For k>1, num1 - k*num2 will be even smaller (since num2 must be > 0).
        // A negative target cannot be a sum of powers of 2.
        if (num1 < num2) {
            return -1;
        }

        // We are looking for the smallest k >= 1 such that:
        // num1 - k * num2 = target, where target can be represented as a sum of k powers of 2.
        // This is possible if and only if:
        // 1. Long.bitCount(target) <= k
        // 2. target >= k

        for (int k = 1; k <= 60; ++k) { // A loop up to 60 is sufficient given the constraints.
            long target = (long)num1 - (long)k * num2;

            // Check if the conditions are met.
            // target must be non-negative to have a bit count.
            // The condition target >= k implies target is non-negative for k>=1.
            if (target >= k && Long.bitCount(target) <= k) {
                return k;
            }
        }

        return -1;
    }
}
```
### Algorithm
1.  First, we need to rephrase the problem into a more manageable form. If we perform `k` operations, we subtract `(2^i_1 + num2) + (2^i_2 + num2) + ... + (2^i_k + num2)` from `num1` to get 0.
2.  This can be written as: `num1 - (2^i_1 + ... + 2^i_k) - k * num2 = 0`.
3.  Rearranging gives: `num1 - k * num2 = 2^i_1 + 2^i_2 + ... + 2^i_k`.
4.  Let `target = num1 - k * num2`. The problem is now to find the minimum `k >= 1` for which `target` can be expressed as a sum of exactly `k` powers of 2.
5.  A positive integer `target` can be written as a sum of `k` powers of 2 if and only if `Long.bitCount(target) <= k` and `k <= target`. `Long.bitCount(target)` gives the minimum number of powers of 2 needed, and `target` is the maximum (by representing `target` as a sum of `target` ones).
6.  We are looking for the minimum `k` that satisfies these two conditions. We can iterate `k` starting from 1 and check the conditions for each `k`.
7.  The first `k` that satisfies `target >= k` and `Long.bitCount(target) <= k` is our answer.
8.  An important observation is that the number of operations `k` does not need to be very large. The number of set bits in a 64-bit integer is at most 64. The condition `k >= Long.bitCount(target)` suggests that `k` is likely small. A loop up to a small constant (e.g., 60) is sufficient because for `k` larger than the number of bits in `target`, the `bitCount` condition is always met, and the problem simplifies, often leading to a contradiction or an already-found solution.
9.  An edge case: if `num1 < num2`, it's impossible to find a solution. This is because for `k=1`, `target = num1 - num2 < 0`, which cannot be a sum of powers of 2. For `k > 1` and `num2 > 0`, the `target` becomes even more negative. Thus, we can return -1 immediately if `num1 < num2`.

# Solutions
### Java

```java
class Solution {
public
  int makeTheIntegerZero(int num1, int num2) {
    for (long k = 1;; ++k) {
      long x = num1 - k * num2;
      if (x < 0) {
        break;
      }
      if (Long.bitCount(x) <= k && k <= x) {
        return (int)k;
      }
    }
    return -1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int makeTheIntegerZero(int num1, int num2) {
    using ll = long long;
    for (ll k = 1;; ++k) {
      ll x = num1 - k * num2;
      if (x < 0) {
        break;
      }
      if (__builtin_popcountll(x) <= k && k <= x) {
        return k;
      }
    }
    return -1;
  }
};

```

### Python

```python
class Solution:
    def makeTheIntegerZero(self, num1: int, num2: int) -> int: for k in count(1): x = num1 - k * num2 if x < 0: break if x . bit_count() <= k <= x: return k return - 1

```