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/
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1)
Space Complexity: O(1)
| 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) |
Number complement | Leetcode #476 • Techdose • 17,260 views views
Watch 9 more video solutions →Practice Number Complement with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor