Watch 10 video solutions for Number Complement, a easy level problem involving Bit Manipulation. This walkthrough by Techdose has 18,021 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 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.
| 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. |