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 < 231
Note: This question is the same as 1009: https://leetcode.com/problems/complement-of-base-10-integer/
Problem Overview: You’re given a positive integer num. The task is to flip every bit in its binary representation, but only up to the most significant bit. Leading zeros are not part of the number, so the complement only affects the bits that actually appear in the binary form.
Approach 1: Bit Manipulation with Mask (O(log n) time, O(1) space)
This approach constructs a bitmask containing all 1s that match the length of num's binary representation. For example, if num = 5 (101 in binary), the mask becomes 111. You build the mask by repeatedly left-shifting and adding 1 until it covers the highest set bit of num. Once the mask is ready, compute the complement using a bitwise XOR: num ^ mask. XOR flips each bit where the mask has 1. This solution relies purely on bit manipulation and works in O(log n) time because the mask is built across the number of bits.
Approach 2: Using Bit Length to Create Mask (O(1) time, O(1) space)
Instead of iteratively building the mask, you can compute the number of bits directly using the bit length of num. If the binary length is k, a mask of k ones is (1 << k) - 1. For instance, if num = 5, its bit length is 3, and the mask becomes (1 << 3) - 1 = 7 (111). The complement is again num ^ mask. This method avoids loops and uses a simple shift operation from bit manipulation combined with bitwise operations. It’s concise and commonly used in production code when the language provides a built‑in bit length function.
Recommended for interviews: The mask construction method is the one most interviewers expect. It demonstrates that you understand how binary representations work and how to manipulate them with shifts and XOR. The bit-length formula is slightly cleaner and faster in practice, but both approaches rely on the same insight: create a mask of all 1s covering the highest set bit, then flip bits using XOR.
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.
We create a mask with all bits set to 1 initially. Then, we shift it left until it has more bits than the input number's binary length. Finally, we XOR the input number with the negated mask.
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.
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.
In this C program, we calculate a mask such that all bits below the highest bit of num are 1. We then XOR num with this mask to get the complement.
Time Complexity: O(1)
Space Complexity: O(1)
According to the problem description, we can use XOR operation to implement the flipping operation, the steps are as follows:
First, we find the highest bit of 1 in the binary representation of num, and the position is denoted as k.
Then, we construct a binary number, where the k-th bit is 0 and the rest of the lower bits are 1, which is 2^k - 1;
Finally, we perform XOR operation on num and the constructed binary number to get the answer.
The time complexity is O(log num), where num is the input integer. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
JavaScript
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Bit Manipulation with Mask | Time Complexity: O(1), the operations are done in constant time as the number of bits is fixed. |
| Using Bit Length to Create Mask | Time Complexity: O(1) |
| Bit Manipulation | — |
| Bit Manipulation. Inversion + AND | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit Manipulation with Mask | O(log n) | O(1) | General interview solution when you want to explicitly build the mask using shifts. |
| Using Bit Length to Create Mask | O(1) | O(1) | When the language provides a built-in bit length function and you want a concise implementation. |
Number complement | Leetcode #476 • Techdose • 18,021 views views
Watch 9 more video solutions →Practice Number Complement with our built-in code editor and test cases.
Practice on FleetCode