Watch 10 video solutions for Complement of Base 10 Integer, a easy level problem involving Bit Manipulation. This walkthrough by Naresh Gupta has 5,643 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |