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.
5 is "101" in binary and its complement is "010" which is the integer 2.Given an integer n, return its complement.
Example 1:
Input: n = 5 Output: 2 Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.
Example 2:
Input: n = 7 Output: 0 Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.
Example 3:
Input: n = 10 Output: 5 Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.
Constraints:
0 <= n < 109Note: This question is the same as 476: https://leetcode.com/problems/number-complement/
The goal of #1009 Complement of Base 10 Integer is to flip every bit in the binary representation of a given non‑negative integer. A key observation is that the complement should only affect the bits within the length of the number’s binary form. For example, if a number uses k bits, we should flip only those k bits rather than all bits of the integer type.
A common bit manipulation strategy is to construct a bitmask consisting of all 1s with the same length as the binary representation of the number. Once the mask is built, applying XOR between the mask and the original number flips the relevant bits efficiently. Another approach is to iterate through each bit and manually build the complemented value.
Be careful with the edge case when the input is 0, since its binary representation requires special handling. These approaches run in time proportional to the number of bits in the integer.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bitmask + XOR | O(log n) | O(1) |
| Bit-by-bit construction | O(log n) | O(1) |
Naresh Gupta
Use these hints if you're stuck. Try solving on your own first.
A binary number plus its complement will equal 111....111 in binary. Also, N = 0 is a corner case.
This approach involves calculating a mask of the same bit length as the number and then using XOR to flip all the bits. The mask is calculated as a sequence of 1s of the same length as the binary representation of the number. For any number 'n', the mask would be computed as (1 << number_of_bits) - 1.
Time Complexity: O(log(n)) as we are shifting bits for the length of the number.
Space Complexity: O(1) since we are using a constant space.
1#include <iostream>
2using namespace std;
3
4int bitwiseComplement(int n) {
5 if (n == 0) return 1;
6 int mask = 0;
7 unsigned int m = n;
8 while (m) {
9 mask = (mask << 1) | 1;
10 m >>= 1;
11 }
12 return (~n) & mask;
13}
14
15int main() {
int n = 5;
cout << bitwiseComplement(n) << endl;
return 0;
}This implementation operates similarly to the C solution. A temporary mask is created to determine the full length of n in binary. Once the full mask of 1s is derived, XOR is used against ~n to derive the complement.
In this approach, instead of calculating a mask using shifts, we use mathematical expressions. We calculate the highest power of 2 greater than n, subtract 1 to get a mask with all 1s up to the highest bit set in n. This mask is then XORed with n for the result.
Time Complexity: O(log(n)) for shifting mask while determining the next power of 2.
Space Complexity: O(1) as only simple variables are used.
1using namespace std;
int bitwiseComplement(int n) {
if (n == 0) return 1;
int mask = 1;
while (mask <= n) mask <<= 1;
return (mask - 1) ^ n;
}
int main() {
int n = 5;
cout << bitwiseComplement(n) << endl;
return 0;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A bitmask ensures that only the bits within the binary length of the number are flipped. Without it, directly applying bitwise NOT would affect extra leading bits in the integer representation.
Yes, variations of bit manipulation problems like this frequently appear in technical interviews. They test understanding of binary representation, bit masks, and efficient low-level operations.
The optimal approach uses bit manipulation by creating a mask of all 1s that matches the length of the number’s binary representation. XORing this mask with the original number flips the relevant bits efficiently without affecting higher bits.
No special data structure is required. The problem is solved using bit manipulation operations such as shifts, XOR, and mask construction, which work directly on integer values.
Using the insights derived from mathematics, the approach is streamlined by directly calculating the complement. We determine the bit-length mask without looping more than necessary, providing an efficient implementation.