Complement of Base 10 Integer
EasyPrompt
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.
- For example, The integer
5is"101"in binary and its complement is"010"which is the integer2.
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/
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves converting the number to its binary string representation, flipping the bits in the string, and then converting the modified binary string back to an integer. It's a straightforward implementation that directly follows the problem's definition.
Algorithm
- Handle the edge case: if
nis 0, return 1. - Convert the integer
nto its binary string representation usingInteger.toBinaryString(n). - Initialize an empty
StringBuilderto store the complement binary string. - Iterate through each character of the binary string.
- If the character is '1', append '0' to the
StringBuilder. - If the character is '0', append '1' to the
StringBuilder. - After the loop, convert the
StringBuilderto a string. - Parse the complement binary string back to an integer (base 10) using
Integer.parseInt(complementString, 2)and return it.
Walkthrough
The core idea is to leverage built-in functions for number-to-string and string-to-number conversions.
- First, we convert the input integer
ninto its binary string equivalent using a function likeInteger.toBinaryString(n). - Then, we iterate through this string. For each character, we flip it: '0' becomes '1' and '1' becomes '0'. We build a new string with these flipped bits using a
StringBuilderfor efficiency. - Finally, we parse this new binary string back into a base-10 integer using
Integer.parseInt(complementString, 2).
For example, if n = 5, Integer.toBinaryString(5) gives "101". We flip the bits to get "010". Integer.parseInt("010", 2) results in 2.
class Solution { public int bitwiseComplement(int n) { if (n == 0) { return 1; } String binaryString = Integer.toBinaryString(n); StringBuilder complementString = new StringBuilder(); for (char c : binaryString.toCharArray()) { if (c == '0') { complementString.append('1'); } else { complementString.append('0'); } } return Integer.parseInt(complementString.toString(), 2); }}Complexity
Time
O(log n). The number of bits in `n` is proportional to `log n`. Converting to and from a string, and iterating through it, all take time proportional to the number of bits.
Space
O(log n). We need extra space to store the binary string representation and the `StringBuilder`. The length of the binary string is proportional to log n.
Trade-offs
Pros
Easy to understand and implement, as it directly follows the problem definition.
Leverages high-level built-in functions, making the code readable.
Cons
Less efficient in terms of both time and space compared to bitwise manipulation approaches.
Involves overhead from string object creation, manipulation, and parsing.
This method avoids string conversions by directly manipulating the bits of the integer. It iterates through each bit of the input number, calculates its complement, and constructs the result number bit by bit.
Algorithm
- Handle the edge case: if
nis 0, return 1. - Initialize
result = 0andpowerOfTwo = 1. - Create a temporary copy of
nto iterate with. - Loop while the temporary number is greater than 0.
- Extract the last bit using
(temp_n & 1). - Flip the bit (e.g.,
1 - last_bit). - Add
flipped_bit * powerOfTwotoresult. - Update
powerOfTwoby left-shifting it by 1 (powerOfTwo <<= 1). - Update the temporary number by right-shifting it by 1 (
temp_n >>= 1). - After the loop, return
result.
Walkthrough
We process the input number n one bit at a time, from the least significant bit (LSB) to the most significant bit (MSB).
We use a result variable to build the complement number and a powerOfTwo variable to place the complemented bits in their correct positions.
In each step of the loop:
- We extract the LSB of
nusing the bitwise AND operation:n & 1. - We flip this bit. If the bit is 1, its complement is 0. If it's 0, its complement is 1. This can be calculated as
1 - (n & 1). - We multiply this flipped bit by the current
powerOfTwoand add it to ourresult. - We then right-shift
nby one (n >>= 1) to discard the LSB and process the next bit in the following iteration. - We update
powerOfTwoby left-shifting it by one (powerOfTwo <<= 1), effectively doubling it for the next bit's position.
The loop continues until n becomes 0, meaning all its bits have been processed. A special case is n = 0, whose complement is 1.
class Solution { public int bitwiseComplement(int n) { if (n == 0) { return 1; } int result = 0; int powerOfTwo = 1; int tempN = n; while (tempN > 0) { // Get the last bit and flip it int lastBit = tempN & 1; int flippedBit = 1 - lastBit; // Add to result result += flippedBit * powerOfTwo; // Move to the next bit powerOfTwo <<= 1; tempN >>= 1; } return result; }}Complexity
Time
O(log n). The loop runs once for each bit in the binary representation of `n`. The number of bits is `floor(log2(n)) + 1`.
Space
O(1). We only use a few extra variables (`result`, `powerOfTwo`, `tempN`), regardless of the size of `n`.
Trade-offs
Pros
More efficient than the string approach, especially in terms of space.
Works directly with the integer representation, avoiding string conversion overhead.
Cons
Slightly more complex to reason about than the direct string conversion.
Still requires a loop, making it less efficient than a constant-time bitmask approach.
This is the most efficient approach. It relies on the property that for any number n, n XOR mask = complement, where mask is a number with the same bit length as n but with all bits set to 1. The problem then reduces to finding this mask and performing a single XOR operation.
Algorithm
- Handle the edge case: if
nis 0, return 1. - Create a bitmask that has the same number of bits as
nand all bits are set to '1'.- Find the highest set bit using
Integer.highestOneBit(n). - The mask is
(Integer.highestOneBit(n) << 1) - 1.
- Find the highest set bit using
- Perform a bitwise XOR operation between
nand themask. - Return the result of the XOR operation.
Walkthrough
The key insight is that flipping bits is equivalent to a bitwise XOR operation with a mask of all 1s. For example, for n = 5 (binary 101), the mask should be 111. 101 XOR 111 gives 010, which is the complement.
The main task is to construct this mask. The mask must have the same number of bits as the binary representation of n.
A clever and fast way to create this mask in Java is to use Integer.highestOneBit(n). This function returns a value with only the most significant bit of n set. For n=10 (1010), Integer.highestOneBit(10) is 8 (1000). The full mask can be constructed by left-shifting this result by one and subtracting one: (Integer.highestOneBit(n) << 1) - 1. This creates a mask of all ones with the correct length (e.g., (8 << 1) - 1 = 16 - 1 = 15, which is 1111 in binary).
Once the mask is found, the complement is simply mask ^ n. The edge case n = 0 must be handled separately, as its complement is 1.
class Solution { public int bitwiseComplement(int n) { if (n == 0) { return 1; } // Find a mask with the same number of bits as n, all set to 1. // e.g., n = 5 (101), highestOneBit is 4 (100). // mask = (4 << 1) - 1 = 8 - 1 = 7 (111). int mask = (Integer.highestOneBit(n) << 1) - 1; // The complement is n XOR mask. // e.g., 5 ^ 7 = 101 ^ 111 = 010 = 2. return n ^ mask; }}Complexity
Time
O(1). Using `Integer.highestOneBit` and other bitwise operations are typically single-instruction, constant-time operations on most hardware.
Space
O(1). No extra space proportional to the input size is required.
Trade-offs
Pros
Extremely fast and efficient, with constant time complexity.
Concise and elegant solution for those familiar with bitwise operations.
Cons
Can be less intuitive for beginners compared to the string-based approach.
Requires understanding of bitwise operators (XOR, shifts) and how to construct a bitmask.
Solutions
Solution
class Solution {public int bitwiseComplement(int n) { if (n == 0) { return 1; } int ans = 0; boolean find = false; for (int i = 30; i >= 0; --i) { int b = n & (1 << i); if (!find && b == 0) { continue; } find = true; if (b == 0) { ans |= (1 << i); } } return ans; }}class Solution {public: int bitwiseComplement(int n) { if (n == 0) return 1; int ans = 0; bool find = false; for (int i = 30; i >= 0; --i) { int b = n & (1 << i); if (!find && b == 0) continue; find = true; if (b == 0) ans |= (1 << i); } return ans; }};class Solution: def bitwiseComplement(self, n: int) -> int: if n == 0: return 1 ans = 0 find = False for i in range(30, - 1, - 1): b = n & (1 << i) if not find and b == 0: continue find = True if b == 0: ans |= 1 << i return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.