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 num, return its complement.
Example 1:
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:
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.
Constraints:
1 <= num < 231Note: This question is the same as 1009: https://leetcode.com/problems/complement-of-base-10-integer/
The key idea in #476 Number Complement is to flip every bit in the binary representation of a positive integer. However, you should only flip the bits that exist in the number’s binary form, ignoring any leading zeros. This makes bit manipulation the most natural approach for solving the problem.
A common strategy is to first determine the position of the most significant bit (MSB). Once you know this, you can create a bitmask consisting entirely of 1s that matches the length of the number’s binary representation. By applying a bitwise operation such as XOR between the number and this mask, you effectively flip all relevant bits.
Another intuitive way is to iterate through each bit and toggle it individually using bit operations. Both methods rely on understanding how binary numbers work and how bitwise operators manipulate them efficiently. Since the operations depend only on the number of bits in the integer, the algorithm runs in constant time with minimal extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Create bitmask up to MSB and apply XOR | O(1) | O(1) |
| Iteratively flip bits using bit operations | O(log n) | O(1) |
Techdose
This approach uses bit manipulation to find the complement. The idea is to create a mask that has the same number of bits set to 1 as the number. By XORing the number with this mask, we effectively flip all the bits.
To create the mask, we can shift 1 left until it exceeds the number and then subtract 1 from it.
Time Complexity: O(1), the operations are done in constant time as the number of bits is fixed.
Space Complexity: O(1), no additional space is used.
1using System;
2
3class Program {
4 public static int FindComplement(int num) {
5 int mask = ~0;
6 while ((num & mask) != 0) mask <<= 1;
7 return ~mask & ~num;
8 }
9
10 static void Main() {
11 Console.WriteLine(FindComplement(5)); // Output: 2
12 Console.WriteLine(FindComplement(1)); // Output: 0
13 }
14}The C# solution uses a bit manipulation strategy similar to C/C++. We use the bitwise mask to XOR the negation of the number to get its complement.
This approach derives a mask by using the bit length of the number. We create a mask by taking 2n - 1, where n is the bit size of the number.
The result of the XOR between num and mask gives the complement.
Time Complexity: O(1)
Space Complexity: O(1)
1#include <iostream>
2
using namespace std;
int findComplement(int num) {
unsigned mask = 1;
while (mask <= num) mask <<= 1;
return (mask - 1) ^ num;
}
int main() {
cout << findComplement(5) << endl; // Output: 2
cout << findComplement(1) << endl; // Output: 0
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
Bit manipulation problems like Number Complement are common in technical interviews, including FAANG-style assessments. While this specific question may not always appear, similar problems that test binary operations and bitmask techniques are frequently asked.
The optimal approach uses bit manipulation by creating a mask of 1s that matches the length of the number’s binary representation. XORing the number with this mask flips all bits at once. This method is efficient and runs in constant time for standard integer sizes.
The problem defines the complement only for the significant bits of the number’s binary representation. Leading zeros are not part of the stored value, so flipping them would incorrectly change the intended result. Therefore, we only flip bits up to the most significant set bit.
No special data structure is required for this problem. The solution relies purely on bitwise operations such as shifting, masking, and XOR, which operate directly on integers.
This C++ solution calculates a mask based on the bit-length and XORs it with the number to find the complement.