Sponsored
Sponsored
This approach uses bit manipulation to find the complement. The idea is to create a mask that has the same number of bits set to 1 as the number. By XORing the number with this mask, we effectively flip all the bits.
To create the mask, we can shift 1 left until it exceeds the number and then subtract 1 from it.
Time Complexity: O(1), the operations are done in constant time as the number of bits is fixed.
Space Complexity: O(1), no additional space is used.
1def find_complement(num):
2 mask = ~0
3 while num & mask:
4 mask <<= 1
5 return ~mask & ~num
6
7print(find_complement(5)) # Output: 2
8print(find_complement(1)) # Output: 0This Python function uses a similar approach with a mask initially set to all 1s, then shifted and XORed with the input number's negation.
This approach derives a mask by using the bit length of the number. We create a mask by taking 2n - 1, where n is the bit size of the number.
The result of the XOR between num and mask gives the complement.
Time Complexity: O(1)
Space Complexity: O(1)
1using System;
2
class Program {
public static int FindComplement(int num) {
int mask = 1;
while (mask <= num) mask <<= 1;
return (mask - 1) ^ num;
}
static void Main() {
Console.WriteLine(FindComplement(5)); // Output: 2
Console.WriteLine(FindComplement(1)); // Output: 0
}
}For C#, the mask is calculated by iteratively left-shifting 1, and then XORed it with num for the complement.