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.
1public class Solution {
2 public int bitwiseComplement(int n) {
3 if (n == 0) return 1;
4
By creating a mask with all bits set to 1, bitwise operations are done against the negation of n to get the complement. This approach efficiently handles the bitwise calculations through shifts and masking.
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.
This Java implementation uses the approach of identifying the mask via powers of two, then calculating the complement by XORing n against the mask. It minimizes operations to derive the precise mask needed.