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.
1def bitwiseComplement(n):
2 if n == 0:
3 return 1
4 mask = 0
5 m = n
6 while
This Python function uses the same approach as previously discussed solutions. A mask of 1s is created, and the complement of n is computed by XOR against this mask.
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.
1
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.
The Python function builds the mask by setting a loop condition within power boundaries, performing all computations efficiently through combined mathematical and bitwise logic.