Complement of Base 10 Integer

To solve this problem, you can follow these steps:

  1. Convert the integer to its binary representation.
  2. Replace every 1 with a 0 and every 0 with a 1 to find the complement.
  3. Convert the binary complement back to an integer and return it.

Here’s how you might implement this in Python:

1
2
3
4

def findComplement(n):
    binary = bin(n).replace("0b", "")  # convert to binary and remove '0b' prefix
    binary_complement = ''.join(['1' if bit == '0' else '0' for bit in binary])  # replace 1 with 0 and 0 with 1
    return int(binary_complement, 2)  # convert back to integer

However, for large inputs this solution might not be efficient. Let’s improve this solution:

The main insight is that for any number in binary, its complement can be found by XORing the number with a string of 1’s of equal length.

1
2
3
4
5

class Solution:
    def bitwiseComplement(self, n: int) -> int:
        length = len(bin(n)) - 2  # get the length of binary representation
        mask = (1 << length) - 1  # create a mask of 1's of the same length
        return n ^ mask  # return the XOR of the input number and the mask

This algorithm performs XOR operation in constant time for each bit, giving a time complexity of O(log n), where n is the input integer. This solution meets the constraints 0 <= n < 109.

Identifying Problem Isomorphism

“Find Complement of an Integer” can be approximately mapped to “Reverse Bits”.

Reasoning: Both problems involve operations on the binary representation of numbers. In “Find Complement of an Integer”, you manipulate the binary representation by flipping the bits, whereas in “Reverse Bits”, you reverse the order of the bits. While the operations differ, the underlying concept of working directly with the binary representation of numbers provides an approximate mapping between the two problems.

While the problems are not exactly isomorphic (they don’t involve the exact same operations or produce the same outputs), they share the concept of bit manipulation, making one a useful reference when trying to understand the other.

“Find Complement of an Integer” is simpler as it involves a straightforward operation on each bit (flipping), whereas “Reverse Bits” requires additional steps to ensure the bits are reversed in the correct order.