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 < 109
Note: This question is the same as 476: https://leetcode.com/problems/number-complement/
Problem Overview: Given a non‑negative integer n, return its complement. The complement flips every bit in the binary representation of n (0 becomes 1, 1 becomes 0) while ignoring leading zeros. For example, 5 (binary 101) becomes 2 (binary 010).
Approach 1: Bit Manipulation Using Mask (O(log n) time, O(1) space)
This method constructs a bit mask that covers exactly the number of bits used by n. First determine the bit length of n by shifting or repeatedly doubling until the mask exceeds the value. A mask like (1 << k) - 1 creates a number with k ones in binary. Once you have the mask, compute the complement with mask ^ n. The XOR flips all bits within that range while leaving higher bits untouched. This approach uses direct bit manipulation operations and runs in O(log n) time because the number of bits in n grows logarithmically.
The key insight: you cannot simply apply ~n because it flips all 32 or 64 bits depending on the language. Creating a mask restricts the operation to the meaningful portion of the binary representation. This is the most common implementation used in interview solutions.
Approach 2: Bit Manipulation Using Math (O(log n) time, O(1) space)
This version builds the complement bit by bit using arithmetic. Iterate through the binary digits of n from least significant to most significant. For each step, check the current bit with n % 2. If the bit is 0, add the corresponding power of two to the result. Then divide n by two and continue. Track the current bit position with a multiplier that doubles each iteration. The resulting number is the complement.
This approach relies more on math-based bit extraction rather than direct bitwise masks. It is useful if you want to explicitly see how each bit is flipped and reconstructed. The complexity remains O(log n) because you process each binary digit once.
Recommended for interviews: The mask-based solution is typically expected. It demonstrates comfort with bitwise operations such as shifts, XOR, and mask construction. The math approach still shows understanding of binary representation but is slightly more verbose. A strong answer explains why ~n alone is incorrect and how the mask limits the complement to the actual bit length.
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.
The function bitwiseComplement checks if the input number is zero, in which case it returns 1 as the complement of 0 is 1. For other numbers, it calculates a mask with all bits set to 1 up to the most significant bit of the number. The complement is then calculated by XORing this mask with the number, flipping all its bits.
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.
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.
This C function calculates (2^x - 1) by left-shifting the mask variable until it is larger than n, then uses XOR to find the complement of n. It's a compact design that minimizes operations while still achieving the same 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.
First, we check if n is 0. If it is, we return 1.
Next, we define two variables ans and i, both initialized to 0. Then we iterate through n. In each iteration, we set the i-th bit of ans to the inverse of the i-th bit of n, increment i by 1, and right shift n by 1.
Finally, we return ans.
The time complexity is O(log n), where n is the given decimal number. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Bit Manipulation Using Mask | Time Complexity: O(log(n)) as we are shifting bits for the length of the number. |
| Bit Manipulation Using Math | Time Complexity: O(log(n)) for shifting mask while determining the next power of 2. |
| Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit Manipulation Using Mask | O(log n) | O(1) | Best general solution. Efficient and uses standard bitwise operations expected in interviews. |
| Bit Manipulation Using Math | O(log n) | O(1) | Useful for understanding how complements form by flipping each binary digit. |
complement of base 10 integer | complement of base 10 integer leetcode | leetcode 1009 | bitwise • Naresh Gupta • 5,643 views views
Watch 9 more video solutions →Practice Complement of Base 10 Integer with our built-in code editor and test cases.
Practice on FleetCode