Complement of Base 10 Integer

EASY

Description

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 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 < 10⁹

Note: This question is the same as 476: https://leetcode.com/problems/number-complement/

Approaches

Checkout 3 different approaches to solve Complement of Base 10 Integer. Click on different approaches to view the approach and algorithm in detail.

String Conversion and Manipulation

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 n is 0, return 1.
Convert the integer n to its binary string representation using Integer.toBinaryString(n).
Initialize an empty StringBuilder to 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 StringBuilder to a string.
Parse the complement binary string back to an integer (base 10) using Integer.parseInt(complementString, 2) and return it.

The core idea is to leverage built-in functions for number-to-string and string-to-number conversions.

First, we convert the input integer n into its binary string equivalent using a function like Integer.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 StringBuilder for 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 Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Complement of Base 10 Integer. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Complement of Base 10 Integer

Patterns:

Bit Manipulation

Companies:

Snap |Cloudera |