Leetcode Daily Question 22/08/2024 - 476. Number Complement

Problem Description:

The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation. For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2. Given an integer num, return its complement.

class Solution:
  def findComplement(self, num: int) -> int:
    result = ""
    bin_rep = bin(num)[2:]
    for bit in bin_rep:
      result += "1" if bit == "0" else "0"
    
    return int(result,2)

Explanation:

This problem can be solved by brute force check of every set bit.

We use the inbuilt python function bin(int) to turn our number into binary form. Recall that python adds the delimiter '0b' in front of the actual binary number to represent which base we are in. So we need to skip those two chars.

The rest of the solution involves flipping the bits manually and turning it back into decimal.

def findComplement(num):
  result = ""
  bin_rep = bin(num)[2:] #skip the delimiter
  for bit in bin_rep:
    result += "1" if bit == "0" else "0" #manually flip the bits
  return int(result,2) #change binary back to decimal

The time complexity of this is O(n), where n is the number of bits in num. The space complexity is also O(n) as we store the flipped binary.

The full solution can be found near the top of the page.