Number Complement Solution

Problem Description

The problem asks us to find the complement of a given integer. The complement is obtained by flipping all the bits (0s to 1s and 1s to 0s) in the binary representation of the integer.

Naive Approach

1. Convert the integer to its binary representation (string).
2. Flip each bit in the binary string.
3. Convert the flipped binary string back to an integer.

Code (Python)

def find_complement_naive(n):
 binary_string = bin(n)[2:]
 flipped_string = ''.join(['1' if bit == '0' else '0' for bit in binary_string])
 return int(flipped_string, 2)

Time Complexity: O(log n)

• Converting to binary string and flipping takes O(log n) time, where n is the input integer.
• Converting the binary string back to an integer takes O(log n) time.

Space Complexity: O(log n)

• The binary string and flipped string each take O(log n) space.

Optimal Approach

A more efficient approach involves bit manipulation. The idea is to create a mask with the same number of bits as the input integer n, but with all bits set to 1. Then, we can XOR the input integer with the mask to flip all the bits.

1. Find the number of bits required to represent the integer n in binary.
2. Create a mask with that many bits set to 1.
3. XOR the integer n with the mask to get the complement.

Code (Python)

def find_complement_optimal(n):
 if n == 0: # Edge case.  0's complement is 0.
 return 0
 num_bits = 0
 temp = n
 while temp > 0:
 num_bits += 1
 temp >>= 1
 mask = (1 << num_bits) - 1
 return n ^ mask

Time Complexity: O(log n)

• Finding the number of bits takes O(log n) time.
• Creating the mask takes O(1) time (bitwise operations are constant time).
• XOR operation takes O(1) time.

Space Complexity: O(1)

• The algorithm uses a constant amount of extra space.

Edge Cases

• n = 0: The complement of 0 is 0.
• n = a power of 2 minus 1: (e.g., n = 7, n = 15) The complement will be 0. This is because the binary representation will be all 1s.

Summary

The optimal approach using bit manipulation is more efficient in terms of space complexity compared to the naive approach that involves string conversions. Both solutions have a time complexity of O(log n), but the bit manipulation approach avoids the overhead of string manipulation, making it slightly faster in practice.