Number Complement — Solution in Python, Java & C++
Number Complement solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on bit manipulation.
Number Complement is an easy coding problem on bit manipulation, asked in Amazon, Adobe and Apple interviews.
- Difficulty: Easy
- Topics: Bit Manipulation
- Asked at: Amazon, Adobe, Apple
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The complement of an integer is what you get by flipping every bit in its binary representation, without any leading zeros.
Given a positive integer num, return its complement.
Example 1
Input: num = 5
Output: 2
Explanation: 101 flips to 010, which is 2.
Example 2
Input: num = 1
Output: 0
Example 3
Input: num = 7
Output: 0
Constraints
1 <= num <= 2147483646
Hints for Number Complement
Hint 1
The trick is not flipping the 32 bits — it is knowing where to stop.
Hint 2
Build a mask of all 1s that is exactly as wide as
num's binary representation.Hint 3
Then the answer is
mask ^ num.
How to solve Number Complement
Build a mask of ones exactly as wide as num, then XOR.
Approach
- Shift
maskleft inserting ones while a copy ofnumis non-zero. - Return
mask ^ num.
Why it works
XOR with all-ones flips every bit; limiting the mask's width keeps leading zeros from becoming ones.
Complexity
- Time —
O(log num) - Space —
O(1)
Pitfalls
- Flipping all 32 bits gives the wrong answer for anything below
2³¹.
Reference solution
Python
def findComplement(num: int) -> int:
mask = 0
v = num
while v:
mask = (mask << 1) | 1
v >>= 1
return mask ^ numJava
public static int findComplement(int num) {
long mask = 0;
long v = num;
while (v > 0) {
mask = mask * 2 + 1;
v /= 2;
}
return (int) (mask - num);
}C++
int findComplement(int num) {
long long mask = 0;
long long v = num;
while (v > 0) {
mask = mask * 2 + 1;
v /= 2;
}
return (int) (mask - num);
}JavaScript
var findComplement = function(num) {
let mask = 0;
let v = num;
while (v > 0) {
mask = (mask << 1) | 1;
v = Math.floor(v / 2);
}
return (mask ^ num) >>> 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 146 bit manipulation problems · the whole catalogue
Learn the technique: Bit Manipulation