Minimum Operations to Make the Integer Zero — LeetCode 2749 Python Solution

The 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.

Example

Input

num1 = 3, num2 = -2

Output

3

Explanation

We can make 3 equal to 0 with the following operations:

Python solution

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

Complexity

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 2749. Minimum Operations to Make the Integer Zero is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Bit Manipulation.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems