Problem

The complement of an integer is the integer you get when you flip all the 0’s to 1’s and all the 1’s 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.

Given an integer num, return its complement.

FYI

This question is the same as 1009: Complement of Base 10 Integer.

Examples

Example 1:

1
2
3

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2:

1
2
3

Input: num = 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

Solution

Video Explanation

Here is the video explanation of this problem.

Method 1 - Subtract From Number with All Ones Larger Than Given Number 🏆

100110, its complement is 011001, the sum is 111111. So we only need get the min number large or equal to num with all ones, and then do subtraction.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int findComplement(int num) {
        int n = 0;
        int i = 0;

        while (n < num) {
            n += Math.pow(2, i);
            i++;
        }

        return n - num;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
	public int findComplement(int num) {
		int n = 0;
		while (n < num) {
			n = (n << 1) | 1;
		}
		return n - num;
	}
}
1
2
3
4
5
6

class Solution:
    def findComplement(self, num: int) -> int:
        n = 0
        while n < num:
            n = (n << 1) | 1
        return n - num

Complexity

  • ⏰ Time complexity: O(log n) — The loop runs once for each bit in num, so the number of iterations is proportional to the number of bits.
  • 🧺 Space complexity: O(1) — Only a constant amount of extra space is used.

Method 2 - Use Highest One Bit Set 🏆

Before this method read this - Bitwise Not or Negation of 16 Bit Integer

  1. The flipped version of the original input but
  2. Only flip N bits within the range from LEFTMOST bit of 1 to RIGHTMOST.

Complexity

  • ⏰ Time complexity: O(1) — Bitwise operations and finding the highest one bit are constant time for fixed-width integers.
  • 🧺 Space complexity: O(1) — Only a constant amount of extra space is used.

Code

1
2
3

public int findComplement(int num) {
	return ~num & ((Integer.highestOneBit(num) << 1) - 1);
}

Dry Run

1
2
3

num =  5 =   0...0101(+)
output = 2 = 0...0010(+) 
num+ans=     0...0111(+)

Make number’s complement:

1

~5 =         1..1010 (-)（all bits inverse）
  • Now we’ve flipped all the bits but it also flipped previously insignificant bits (0s), so to revert them back to 0s, we need to only keep the significant bits and turn off the insignificant bits
  • This can be done by using mask of 1s having size equal to number of bits in num. This mask is (1 « nBits) - 1
  • This is a standard mask in bit manipulation problems
1
2
3

mask = (Integer.highestOneBit(num) << 1) - 1 = 1000-1=0..0111(+)

~num & mask = (1...1010) & (0...0111) = 0...0010 [Ans]

Variant 1

1
2
3
4
5

public int findComplement(int num) {
	var nBits = (int) Math.floor((Math.log(num) / Math.log(2)) + 1);
	var mask = (1 << nBits) - 1;
	return ~num & mask;
}

Code

1
2
3
4

class Solution:
    def findComplement(self, num: int) -> int:
        mask = (1 << num.bit_length()) - 1
        return ~num & mask

Method 3 - Using Complement and Adition

To find complement of num = 5 which is 101 in binary. First ~num gives ...11111010 but we only care about the rightmost 3 bits. Then to erase the 1s before 010 we can add 1000

Code

1
2
3

public int findComplement(int num) {
	return ~num + (Integer.highestOneBit(num) << 1);
}
1
2
3
4

class Solution:
    def findComplement(self, num: int) -> int:
        mask = (1 << num.bit_length())
        return ~num + mask

Complexity

  • ⏰ Time complexity: O(1) — All operations (bitwise NOT, addition, highestOneBit) are constant time for fixed-width integers.
  • 🧺 Space complexity: O(1) — Only a constant amount of extra space is used.

Method 4 - Using Xor between number and all ones

We can also do:

  1. Convert the integer to its binary representation.
  2. Flip all the bits in the binary representation.
  3. Convert the resulting binary string back to an integer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public class Solution {
    public int findComplement(int num) {
        // Find the number of bits in the given number
        int bitLength = Integer.toBinaryString(num).length();

        // Create a mask with all bits set to 1 of the same length as the binary
        // representation of num
        int mask = (1 << bitLength) - 1;

        // XOR num with the mask to flip all bits
        return num ^ mask;
    }
}
1
2
3
4

class Solution:
    def findComplement(self, num: int) -> int:
        mask = (1 << num.bit_length()) - 1
        return num ^ mask

Complexity

  • ⏰ Time complexity: O(log n) — Calculating the bit length requires converting to binary, which takes time proportional to the number of bits.
  • 🧺 Space complexity: O(1) — Only a constant amount of extra space is used.