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.
1function findComplement(num) {
2 let mask = ~0;
3 while (num & mask) mask <<= 1;
4 return ~
The JavaScript solution involves using a mask initialized to all 1s, left shifted, and then XORed with the negation of the input number.
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)
1function
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.
In JavaScript, we find a mask by left-shifting until it surpasses num, and XOR to get the complement.