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
5
6
7

Input: num1 = 3, num2 = -2
Output: 3
Explanation: We can make 3 equal to 0 with the following operations:
- 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

The operation subtracts (2^i + num2) from num1. To reach zero, we need to find a sequence of such operations. The key is to notice that after k operations, num1 + k * num2 must be a sum of k powers of two, i.e., it must be possible to write num1 + k * num2 as a sum of k distinct powers of two (which is equivalent to having at least k bits set in its binary representation).

Approach

  1. For k from 1 to 60, check if num1 + k * num2 > 0 and has at least k bits set.
  2. For each k, if num1 + k * num2 > 0 and the number of set bits in its binary representation is less than or equal to k, then k is a possible answer.
  3. Return the minimum such k, or -1 if impossible.
  4. Edge case: If num2 is positive and num1 is small, it may never reach zero.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int minOperations(int num1, int num2) {
        for (int k = 1; k <= 60; ++k) {
            long long x = num1 + 1LL * k * num2;
            if (x <= 0) continue;
            if (__builtin_popcountll(x) <= k) return k;
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

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

class Solution {
    fun minOperations(num1: Int, num2: Int): Int {
        for (k in 1..60) {
            val x = num1.toLong() + k * num2.toLong()
            if (x <= 0) continue
            if (x.countOneBits() <= k) return k
        }
        return -1
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def minOperations(self, num1: int, num2: int) -> int:
        for k in range(1, 61):
            x = num1 + k * num2
            if x <= 0:
                continue
            if bin(x).count('1') <= k:
                return k
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

class Solution {
    minOperations(num1: number, num2: number): number {
        for (let k = 1; k <= 60; k++) {
            const x = num1 + k * num2;
            if (x <= 0) continue;
            if (x.toString(2).split('1').length - 1 <= k) return k;
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(60) — 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.