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/
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
complement of base 10 integer | complement of base 10 integer leetcode | leetcode 1009 | bitwise • Naresh Gupta • 5,294 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