LC-2749 Medium LeetCode

2749. Minimum Operations to Make the Integer Zero

Bit Manipulation Brainteaser Enumeration

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 30% Topics: Bit Manipulation, Brainteaser, Enumeration

Reading material

Bit Manipulation 10 min Game Theory 11 min Backtracking 14 min

Reference solution (spoiler · python)

# Time:  O(1)
# Space: O(1)

# math, linear search, bit manipulations
class Solution(object):
    def makeTheIntegerZero(self, num1, num2):
        """
        :type num1: int
        :type num2: int
        :rtype: int
        """
        def popcount(x):
            result = 0
            while x:
                x &= (x-1)
                result += 1
            return result

        for i in xrange(1, 60+1):
            if num1-i*num2 < 0:
                break
            if popcount(num1-i*num2) <= i <= num1-i*num2:
                return i
        return -1

Solution from kamyu104/LeetCode-Solutions · MIT