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.
VIDEO
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 substraction.
Code#
Java
Math.pow Is Slower, So Lets Use Left Shift:
Java
Python
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
The flipped
version of the original input
but
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#
Java
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;
}
Python#
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 1
s before 010
we can add 1000
Code#
Java
Python
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:
Convert the integer to its binary representation.
Flip all the bits in the binary representation.
Convert the resulting binary string back to an integer.
Code#
Java
Python
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.