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.
1public class Main {
2 public static int findComplement(int num) {
3 int mask = ~0;
4 while ((num & mask) != 0) mask <<= 1;
5 return ~mask & ~num;
6 }
7
8 public static void main(String[] args) {
9 System.out.println(findComplement(5)); // Output: 2
10 System.out.println(findComplement(1)); // Output: 0
11 }
12}In Java, similar to C/C++, we use a mask of all 1s, shift it left and XOR 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)
1#include <iostream>
2
using namespace std;
int findComplement(int num) {
unsigned mask = 1;
while (mask <= num) mask <<= 1;
return (mask - 1) ^ num;
}
int main() {
cout << findComplement(5) << endl; // Output: 2
cout << findComplement(1) << endl; // Output: 0
return 0;
}This C++ solution calculates a mask based on the bit-length and XORs it with the number to find the complement.