Solution: Complement of Base 10 Integer

Let's solve the Complement of Base 10 Integer problem using the Bitwise Manipulation pattern.

We'll cover the following

Statement

For any nn number in base 10, return the complement of its binary representation as an integer in base 10.

Constraints

  • 0≤n≤1090 \leq n \leq 10^9

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

To calculate the complement of any integer, we need to perform the following steps:

  1. Convert the integer to its binary value.

  2. Once we have the binary value, we can use a loop to incrementally convert each 11 to 00 and each 00 to 11.

  3. Now that we have the complemented binary number, we can convert it to its respective base 10 value.

The conversion of binary values from 11 to 00 and 00 to 11 can take up to ⌊log⁡n⌋+1\lfloor \log{n} \rfloor + 1 iterations, where ⌊log⁡n⌋+1\lfloor \log{n} \rfloor + 1 is the length of binary value of the base 10 number. So, the time complexity of this approach is O(log⁡n)O(\log{n}). Since the number of bits needed to hold the binary value is ⌊log⁡n⌋+1\lfloor \log{n} \rfloor + 1, the space complexity of this approach is also O(log⁡n)O(\log{n}).

Optimized approach using bitwise manipulation

This approach uses bitwise XOR operations, which outputs 11 only when the two bits compared are different and 00 when they are the same. It XORs the binary value of the number with a bitmask composed entirely of 1s1s. The length of the bitmask is equal to the bit length of the original number, ensuring each bit is flipped: 0s0s become 1s1s, and 1s1s become 0s0s. After taking XOR, it converts the binary value back to base 1010 to get the final answer.

The following illustration demonstrates the algorithm:

Press + to interact
canvasAnimation-image
1 of 5

The primary goal here is to flip all the bits of a number. Here’s how we’ll implement this algorithm:

  1. Calculate the number of bits required to store a certain integer. We can get this by rounding down log⁡n\log{n} and adding 11.

  2. Create an all 1-bit bitmask against the number of bits of the input value. For example, if we need 44 bits to represent an integer, all its set bits will be 1111. The decimal value of 1111 =23+22+21+20=15= 2^3 + 2^2 + 2^1 + 2^0 = 15, which is equal to 2bits−1=24−12^{bits} - 1 = 2^4 - 1. So, we can use this formula to get the required number.

  3. Flip all occurrences of 11s to 00s and 00s to 11s by computing the XOR operation between the two numbers.

Let’s look at the code for this solution below:

class ComplementNumber {
    public static int findBitwiseComplement(int num) {
        if (num == 0) {
            return 1;
        }
        int bitCount = (int) Math.floor((int)(Math.log(num) / Math.log(2))) + 1;
        int allBitsSet = (1 << bitCount) - 1;
        return num ^ allBitsSet;
    }
    public static void main(String[] args) {
        int[] decimalValues = {42, 233, 100, 999999, 54};
        for (int i = 0; i < decimalValues.length; i++) {
            System.out.print(i + 1);
            System.out.print(".\tInput: " + decimalValues[i]);
            System.out.print("\n\tBitwise complement of " + decimalValues[i] + " is: ");
            System.out.println(findBitwiseComplement(decimalValues[i]));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Complement of Base 10 Integer

Solution summary

To recap, the solution to this problem can be divided into the following parts:

  1. We calculate the number of bits required to store any number.

  2. We create an all 1-bit bitmask against it and flip all occurrences of 11s to 00s and 00s to 11s by computing the XOR operation.

  3. By converting the binary value back to base 10, we got our final answer.

Time complexity

To take the complement, we first calculate the number of bits required for the binary representation of the given integer and then take XOR, which are constant time operations. So, the time complexity of this solution is O(1)O(1).

Space complexity

The space complexity of this solution is O(1)O(1) because at any time we have a decimal number to have it converted into its complement.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.