Bit Manipulation with Python

QA/SDET/SWE Binary Interview Questions — 5 LeetCode Solutions

Today, let’s solve a few binary LeetCode problems with Python.

191. Number of 1 Bits

Solution

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += n % 2
            n = n >> 1
        return res

# Test the function
solution = Solution()
print(solution.hammingWeight(11)
print(solution.hammingWeight(128)
print(solution.hammingWeight(2147483645)

# Time: O(1)  - The run time depends on the number of bits in n. Because n in this piece of code is a 32-bit integer, the time complexity is O(1).
# Space: O(1) - No additional space is allocated.

The above algorithm is efficient, but it traverses through every bit in the in the integer — either 0 or 1. We can optimize slightly by counting only the 1 bits. The below modified algorithm will only run as many times as there are 1s in the input:

class Solution:
    def hammingWeight(self, n: int) -> int:
        while n: 
            n &= (n - 1)
            res += 1
        return res

We can also solve the problem with a 1-liner in Python:

class Solution:
    def hammingWeight(self, n: int) -> int:
        return bin(n).count('1')

338. Counting Bits

Solution

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n + 1)
        offset = 1

        for i in range(1, n + 1):
            if offset * 2 == i:
                 offset = i
            dp[i] = 1 + dp[i - offset]
        
        return dp

# Test the function
solution = Solution()
print(solution.countBits(2)
print(solution.countBits(5)

# Time: O(n)
# Space: O(n)

190. Reverse Bits

Solution

class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        for i in range(32):
            bit = (n >> i) & 1
            res = res | (bit << (31 - i))
        return res

# Test the function
solution = Solution()
print(solution.reverseBits(00000010100101000001111010011100)
print(solution.reverseBits(11111111111111111111111111111101)

# Time: O(1) - constant time, b/c we're guaranteed there are 32 bits. The solution is not going to scale, regardless of whatever the input n is, as long as it's 32 bits.
# Space: O(1) - the memory we're using is just a single variable res.

268. Missing Number

Solution

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        res = len(nums)
        for i in range(res):
            res += (i - nums[i])  # sum([0,1,2,3]) - sum([0,1,3]) = 2
        return res

# Test the function
solution = Solution()
print(solution.missingNumber([3,0,1])
print(solution.missingNumber([0,1])
print(solution.missingNumber([9,6,4,2,3,5,7,0,1])


# Time: O(n) - Taking the sum of each array is O(2n) or O(n).
# Space: O(1) - We only maintain 2 sums for each of these array, we don't actually use any extra memory, so the overall memory complexity is O(1).

We can compute the sum using Gauss’ formula:

class Solution:
    def missingNumber(self, nums):
        expected_sum = len(nums) * (len(nums) + 1) // 2
        actual_sum = sum(nums)
        return expected_sum - actual_sum

# Time: O(n) - although Gauss' formula can be computed in O(1) time, summing nums costs us O(n) time, so the algorithm is overall linear. 
# Space: O(1) - we only push a few integers around, so it has constant memory usage.

371. Sum of Two Integers

Solution

class Solution:
    def getSum(self, a: int, b: int) -> int:
        x, y = abs(a), abs(b)
        if x < y:
            return self.getSum(b, a)  
        sign = 1 if a > 0 else -1
        
        if a * b >= 0:
            while y:
                x, y = x ^ y, (x & y) << 1
        else:
            while y:
                x, y = x ^ y, ((~x) & y) << 1
        
        return x * sign

# Test the function
solution = Solution()
print(solution.getSum(1,2)
print(solution.getSum(2,3)

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

Hope you find these solutions helpful. If you do, please make sure to follow me on LinkedIn, X , GitHub, or IG.