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.
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; }}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.