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.
1#include <stdio.h>
2
3int findComplement(int num) {
4 unsigned mask = ~0;
5 while (num & mask) mask <<= 1;
6 return ~mask & ~num;
7}
8
9int main() {
10 printf("%d\n", findComplement(5)); // Output: 2
11 printf("%d\n", findComplement(1)); // Output: 0
12 return 0;
13}We create a mask with all bits set to 1 initially. Then, we shift it left until it has more bits than the input number's binary length. Finally, we XOR the input number with the negated mask.
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)
1def find_complement
This Python function computes the mask based on the input's bit length, then returns the complement by XORing.