Educative: Interactive Courses for Software Developers

Statement#

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

Constraints

$0 \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:

Convert the integer to its binary value.
Once we have the binary value, we can use a loop to incrementally convert each $1$ to $0$ and each $0$ to $1$ .
Now that we have the complemented binary number, we can convert it to its respective base 10 value.

The conversion of binary values from $1$ to $0$ and $0$ to $1$ can take up to $\lfloor \log{n} \rfloor + 1$ iterations, where $\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})$ . Since the number of bits needed to hold the binary value is $\lfloor \log{n} \rfloor + 1$ , the space complexity of this approach is also $O(\log{n})$ .

Optimized approach using bitwise manipulation#

This problem is a classic example of when to use the bitwise manipulation pattern. We will use the XOR ( $\land$ ) properties to get the complement of any $n$ number. The XOR (exclusive OR) operation is a binary operation that results in true (or 1) only when the inputs are different and false (or 0) if the inputs are the same. By taking the bitwise XOR of the binary value of the number with an all 1-bit bitmask, each of the bits in the binary value will be flipped, resulting in the complement of the number.

The following illustration demonstrates the algorithm:

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

Calculate the number of bits required to store a certain integer. We can get this by rounding down $\log{n}$ and adding $1$ .
Create an all 1-bit bitmask against the number of bits of the input value. For example, if we need $4$ bits to represent an integer, all its set bits will be 1111. The decimal value of 1111 $= 2^3 + 2^2 + 2^1 + 2^0 = 15$ , which is equal to $2^{bits} - 1 = 2^4 - 1$ . So, we can use this formula to get the required number.
Flip all occurrences of $1$ s to $0$ s and $0$ s to $1$ s by computing the XOR operation between the two numbers.

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

from math import log2, floor
def find_bitwise_complement(num):
    if num == 0:
        return 1
    bit_count = floor(log2(num)) + 1
    all_bits_set = (1 << bit_count) - 1
    return num ^ all_bits_set
# driver code
def main():
    decimal_values = [42, 233, 100, 999999, 54]
    for i in range(len(decimal_values)):
        print(i + 1, ".\t Input: ", decimal_values[i], sep="")
        print(f'\t Bitwise complement of {decimal_values[i]} is: ', find_bitwise_complement(decimal_values[i]), sep="")
        print("-" * 100)
if __name__ == '__main__':
    main()

Enter to Rename, Shift+Enter to Preview

Complement of Base 10 Number

Solution summary#

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

We calculate the number of bits required to store any number.
We create an all 1-bit bitmask against it and flip all occurrences of $1$ s to $0$ s and $0$ s to $1$ s by computing the XOR operation.
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)$ .

Space complexity#

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

Solution: Complement of Base 10 Number