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 theminimum number of operations needed to make num1 equal to 0.

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

Examples

Example 1

1
2
3
4

- We choose i = 2 and substract 22 + (-2) from 3, 3 - (4 + (-2)) = 1.
- We choose i = 2 and substract 22 + (-2) from 1, 1 - (4 + (-2)) = -1.
- We choose i = 0 and substract 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

1
2
3

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 <= 10^9
  • -109 <= num2 <= 10^9

Solution

Method 1 – Bit Manipulation & Enumeration

Intuition

After a bit of playing around, it seems hard to find an explicit formula for the answer. As with many computer science problems, we can instead try to search over the answer space, trading runtime for ease of implementation.

To make num1 equal to zero, we perform a series of operations. We start by subtracting num2 from num1, and then subtract powers of two (2^k1, 2^k2, and so on) from the result.

When we rearrange the equation, we get:

`num1 - k * num2 - (2^k1 + 2^k2 + ...) == 0`

This equation states that num1 can be expressed as the sum of k times num2 and the sum of powers of two.

The goal is to find the values of k and the powers of two that make num1 equal to zero. By subtracting num2 and powers of two from num1 in each step, we aim to reduce the remaining value to zero.

Therefore, the problem becomes finding the minimum combination of k and the powers of two needed to reach zero.

Why checking bits and steps

Checking the number of set bits (bits): The count of set bits in the diff value represents the number of powers of two needed to construct the remaining value after subtracting num2 * steps from num1. Recall that each power of two corresponds to an operation. If the count of set bits is less than or equal to the current step, it means that we have enough powers of two to perform the required operations within the given step count.

Checking if the step falls within the range of diff: The range of diff represents the remaining value after subtracting num2 * steps from num1. If the current step falls within this range, it indicates that we can continuously subtract powers of two from the remaining value until it becomes zero. By ensuring the step falls within the range, we confirm that the remaining value can be reduced to zero using the given number of steps.

By checking both conditions, we ensure that we have enough powers of two and a valid range to perform the necessary operations and make num1 equal to zero. If both conditions are met, the function returns the minimum number of steps required. Otherwise, it continues to the next iteration to check for other possible step counts.

In summary, the conditions of checking the number of set bits and the range of diff validate the feasibility of making num1 zero within the given step count and help in determining the minimum number of steps required.

Approach

target := num1 - k * num2 = 2^i1 + 2^i2 + … + 2^ik

We can test whether or not k operations is sufficient for some given k.

If k operations are used, then:

1
2

num1 = (num2 + 2^i1) + (num2 + 2^i2) + ... + (num2 + 2^ik)
= k * num2 + (2^i1 + 2^i2 + ... + 2^ik)

for some i1, i2, …, ik in [0, 60].

Rearranging, this gives:

1

target := num1 - k * num2 = 2^i1 + 2^i2 + ... + 2^ik

Observe that we can construct any positive integer x with at least x.bit_count() powers of two and at most x powers of two. This is because we can start with the powers of two that make up the bits of x, then continue to split apart larger powers of two into smaller powers of two until we are left with just 1’s. For instance, 5 = 4 + 1 = (2 + 2) + 1 = 2 + (1 + 1) + 1 = (1 + 1) + 1 + 1 + 1. Thus, we must have target.bit_count() <= k <= target.

Using the above algorithm to determine whether a certain number of operations is valid, we can do a linear search through all possible number of operations in [0,60] and take the minimum valid answer.

Why the answer is bounded from above by 60

target < 0, target.bit_count() > k, or k > target.

Assume there is no valid answer for k <= 60. Then, at least one of the following hold for k = 60:

1
2
3

target < 0,
target.bit_count() > k, or
k > target.

(2) is impossible since target := num1 - k * num2 is bounded from above by the input constraints.

If (1) is true, then num1 - k * num2 < 0 implies num2 > 0, meaning target is strictly decreasing while k is strictly increasing. If we have not found a solution by this point, this implies there is no solution past 60.

If (3) is true, k > num1 - k * num2 implies k * (num2 + 1) > num1, meaning either num2 = 0, in which case k = num1.bit_count() will have previously been a valid answer, or num2 > 0. Again, target is strictly decreasing while k is strictly increasing; there is no solution.

In all cases, there is either a contradiction or no solution; k is bounded from above. As a matter of fact, there can be a tighter bound on k as long as the argument for (2) holds.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int makeTheIntegerZero(int num1, int num2) {
        for (int k = 0; k <= 60; ++k) {
            long long target = num1 - 1LL * k * num2;
            if (target >= 0 && __builtin_popcountll(target) <= k && k <= target) {
                return k;
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9

func makeTheIntegerZero(num1 int, num2 int) int {
    for k := 0; k <= 60; k++ {
        target := int64(num1) - int64(k)*int64(num2)
        if target >= 0 && bits.OnesCount64(uint64(target)) <= k && k <= int(target) {
            return k
        }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int makeTheIntegerZero(int num1, int num2) {
        for (int k = 0; k <= 60; k++) {
            long target = num1 - 1L * k * num2;
            if (target >= 0 && Long.bitCount(target) <= k && k <= target) {
                return k;
            }
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun makeTheIntegerZero(num1: Int, num2: Int): Int {
        for (k in 0..60) {
            val target = num1.toLong() - k * num2.toLong()
            if (target >= 0 && target.countOneBits() <= k && k <= target) {
                return k
            }
        }
        return -1
    }
}
1
2
3
4
5
6
7

class Solution:
    def makeTheIntegerZero(self, num1: int, num2: int) -> int:
        for k in range(61):
            target = num1 - k * num2
            if target >= 0 and target.bit_count() <= k <= target:
                return k
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn make_the_integer_zero(num1: i32, num2: i32) -> i32 {
        for k in 0..=60 {
            let target = num1 as i64 - k as i64 * num2 as i64;
            if target >= 0 && target.count_ones() as i32 <= k && k as i64 <= target {
                return k as i32;
            }
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    makeTheIntegerZero(num1: number, num2: number): number {
        for (let k = 0; k <= 60; k++) {
            const target = num1 - k * num2;
            const bitCount = target >= 0 ? target.toString(2).split('1').length - 1 : 0;
            if (target >= 0 && bitCount <= k && k <= target) {
                return k;
            }
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(60) = O(1) — We check up to 60 possible values for k, and for each, count bits in a number.
  • 🧺 Space complexity: O(1) — Only a few variables are used, no extra space proportional to input size.