Number Complement
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 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/
Approaches
3 approaches with complexity analysis and trade-offs.
This approach is the most straightforward, as it directly follows the problem's definition. It involves converting the number to a binary string, flipping the characters of the string ('0's to '1's and vice-versa), and then converting the modified binary string back to an integer.
Algorithm
- Convert the input integer
numto its binary string representation using a built-in function likeInteger.toBinaryString(num). - Create a new
StringBuilderto construct the complemented binary string. - Iterate through each character of the original 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 this new binary string back to an integer using base 2, for example, with
Integer.parseInt(complementedString, 2). - Return the final integer.
Walkthrough
The core of this method lies in leveraging built-in functions for number-to-string and string-to-number conversions. First, we get the binary representation of num as a string. Then, we iterate over this string, building a new string which is the bitwise complement of the original. Finally, this new binary string is parsed back into an integer, which is our result.
class Solution { public int findComplement(int num) { String binaryString = Integer.toBinaryString(num); StringBuilder complementBuilder = new StringBuilder(); for (char c : binaryString.toCharArray()) { if (c == '1') { complementBuilder.append('0'); } else { complementBuilder.append('1'); } } return Integer.parseInt(complementBuilder.toString(), 2); }}Complexity
Time
O(log n). The time complexity is dominated by the conversion to and from the binary string, as well as the iteration. The number of bits in `num` is proportional to log(num).
Space
O(log n). The space is required to store the binary string representation of the number `num` and the `StringBuilder`. The length of the binary string is proportional to log(num).
Trade-offs
Pros
Very easy to understand and implement.
The logic directly maps to the problem description.
Cons
Relatively inefficient due to the overhead of creating and manipulating string objects.
Involves multiple conversions (integer to string, string to integer) which are computationally more expensive than bitwise operations.
A more optimized approach is to avoid string conversions and work directly with the bits of the integer. We can process the number bit by bit, from least significant to most significant. In each step, we flip the current bit and add its corresponding value to a running total which will be our final result.
Algorithm
- Initialize
resultto 0 andpowerOfTwoto 1.powerOfTwowill track the value of the current bit position (1, 2, 4, ...). - Make a copy of
numto iterate with, let's call ittemp. - Loop while
tempis greater than 0:- Extract the least significant bit (LSB) of
tempusingtemp & 1. - Flip the LSB:
flippedBit = lsb ^ 1. - Add the flipped bit's value to the result:
result += flippedBit * powerOfTwo. - Update
powerOfTwofor the next position by left-shifting it:powerOfTwo <<= 1. - Update
tempby right-shifting it to process the next bit:temp >>= 1.
- Extract the least significant bit (LSB) of
- After the loop terminates,
resultwill hold the integer value of the complement.
Walkthrough
This method iteratively builds the complement number. We use a loop that continues as long as there are bits left to process in the input number. Inside the loop, we isolate the last bit, flip it, and then add its positional value (e.g., 1, 2, 4, 8...) to our result. We use a powerOfTwo variable, starting at 1 and doubling in each iteration, to calculate this positional value. The input number is right-shifted in each iteration to expose the next bit.
class Solution { public int findComplement(int num) { int result = 0; long powerOfTwo = 1; // Use long to avoid overflow for large num int temp = num; while (temp > 0) { // Get the least significant bit (0 or 1) int lsb = temp & 1; // Flip the bit (0 becomes 1, 1 becomes 0) int flippedLsb = lsb ^ 1; // Add the value of the flipped bit to the result result += flippedLsb * powerOfTwo; // Move to the next bit position powerOfTwo <<= 1; temp >>= 1; } // Handle the edge case where num is 0, though constraints prevent this. // If num was 0, the loop wouldn't run, returning 0. The complement of 0 is 1. // A simple fix would be `if (num == 0) return 1;` return result; }}Complexity
Time
O(log n). The loop runs once for each bit in the binary representation of `num`. The number of bits is proportional to log(num).
Space
O(1). We only use a few variables to store the result and loop counters, regardless of the size of the input number.
Trade-offs
Pros
More efficient than the string-based approach.
Uses constant extra space, O(1).
Cons
Requires a loop that iterates through each bit, which is less performant than a constant-time bitmasking solution.
The most efficient solution uses bitwise operations to compute the complement in constant time (for a fixed-size integer). The logic relies on the property that num XOR mask = complement, where the mask is a sequence of 1s with the same bit-length as num. The main task is to construct this mask efficiently.
Algorithm
- The key idea is that
num XOR mask = complement, wheremaskis a number with the same bit-length asnumbut with all bits set to 1. - Step 1: Create the mask. An efficient way to create this mask is needed.
- Use
Integer.highestOneBit(num)to get an integer with only the most significant bit ofnumset. Fornum=5(101), this gives 4 (100). - Create the full mask by shifting this value left by one and subtracting one:
mask = (Integer.highestOneBit(num) << 1) - 1. Fornum=5, this is(4 << 1) - 1 = 7(111).
- Use
- Step 2: Calculate the complement.
- Perform a bitwise XOR between
numand themask:result = num ^ mask.
- Perform a bitwise XOR between
- Alternative Step 2:
- Flip all 32 bits of
numusing the NOT operator:~num. - Use the mask to turn off the unwanted leading 1s:
result = ~num & mask.
- Flip all 32 bits of
- Return the result.
Walkthrough
This approach finds the complement by first creating a bitmask. This mask has its bits set to 1 for all positions up to the most significant bit of the input number num. For example, if num is 5 (binary 101), its bit-length is 3, so the required mask is 111 (decimal 7). Once this mask is obtained, the complement can be found simply by XORing the number with the mask (num ^ mask).
A highly efficient way to create this mask in Java is by using Integer.highestOneBit(num). This function returns a value with only the single highest-order '1' bit from num. By shifting this value left by one and subtracting one, we get our desired mask.
class Solution { public int findComplement(int num) { // Create a mask that has 1s up to the most significant bit of num. // For num = 5 (101), highestOneBit is 4 (100). // The mask becomes (4 << 1) - 1 = 7 (111). int mask = (Integer.highestOneBit(num) << 1) - 1; // The complement is num XORed with the mask. // 5 ^ 7 = (101) ^ (111) = 010 = 2. return num ^ mask; }}Alternatively, one could use the bitwise NOT operator ~ and the mask.
class Solution { public int findComplement(int num) { int mask = (Integer.highestOneBit(num) << 1) - 1; // ~num flips all 32 bits. The mask is used to clear the leading bits. // ~5 is ...11111010. mask is ...00000111. // (~5) & mask = ...00000010 = 2. return ~num & mask; }}Complexity
Time
O(1). For a 32-bit integer, the number of operations is constant. Functions like `Integer.highestOneBit` are often implemented as hardware intrinsics, making them very fast.
Space
O(1). This approach uses a fixed number of variables, so its space usage is constant.
Trade-offs
Pros
Extremely efficient, performing the calculation in constant time.
Uses constant space.
Elegant and concise for those familiar with bitwise operations.
Cons
The bit manipulation logic, especially for creating the mask, can be less intuitive for those not familiar with bitwise operations.
Solutions
Solution
class Solution {public int findComplement(int num) { int ans = 0; boolean find = false; for (int i = 30; i >= 0; --i) { int b = num & (1 << i); if (!find && b == 0) { continue; } find = true; if (b == 0) { ans |= (1 << i); } } return ans; }}/** * @param {number} num * @return {number} */ var findComplement = function ( num,) { return num ^ (2 ** num.toString(2).length - 1);};class Solution {public: int findComplement(int num) { int ans = 0; bool find = false; for (int i = 30; i >= 0; --i) { int b = num & (1 << i); if (!find && b == 0) continue; find = true; if (b == 0) ans |= (1 << i); } return ans; }};class Solution: def findComplement( self, num: int) -> int: return num ^ (2 ** (len(bin(num)[2:])) - 1)Video 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.