The complement of an integer is the integer you get when you flip all the 0’s to 1 ‘s and all the 1s to 0’s in its binary representation.

For example, The integer 5 is “101” in binary and its complement is “010” which is the
integer 2.

Explore Free Engineering Handwritten Notes!

Looking for comprehensive study materials on Python, Data Structures and Algorithms (DSA), Object-Oriented Programming (OOPs), Java, Software Testing, and more?

Download Now

We earn a commission if you make a purchase, at no additional cost to you.

class Solution {
public:
   int bitwiseComplement(int n) {
   int m = n;
   int mask = 0;

    //edge case
    if(n== 0)
     return 1;
    while( m!=0) {
       mask = (mask << 1) | 1;
       m = m >> 1;
}
    int ans = (~n) & mask;
    return ans;
}

Approach: Here the number is converted by flipping bits and adding that power of 2 to the answer. Follow the steps mentioned below to implement it:

• Find the binary representation of N.
• For each bit, flip it and add the contribution of this bit to the final answer.
• Return the final answer

Time Complexity: O(logN)
Auxiliary Space: O(1)