Solution: Complement of Base 10 Number

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Complement of Base 10 Number

Table of Contents

Contents are not accessible

Problem Statement

Every non-negative integer N has a binary representation, for example, 8 can be represented as “1000” in binary and 7 as “0111” in binary.

The complement of a binary representation is the number in binary that we get when we change every 1 to a 0 and every 0 to a 1. For example, the binary complement of “1010” is “0101”.

For a given positive number N in base-10, return the complement of its binary representation as a base-10 integer.

Example 1:

Input: 8
Output: 7
Explanation: 8 is 1000 in binary, its complement is 0111 in binary, which is 7 in base-10.

Example 2:

Input: 10
Output: 5
Explanation: 10 is 1010 in binary, its complement is 0101 in binary, which is 5 in base-10.

Constraints:

1 <= n < 10<sup>9</sup>

Solution

Recall the following properties of XOR:

It will return 1 if we take XOR of two different bits i.e. 1^0 = 0^1 = 1.
It will return 0 if we take XOR of two same bits i.e. 0^0 = 1^1 = 0. In other words, XOR of two same numbers is 0. 3.It returns the same number if we XOR with 0.

From the above-mentioned first property, we can conclude that XOR of a number with its complement will result in a number that has all of its bits set to 1. For example, the binary complement of “101” is “010”; and if we take XOR of these two numbers, we will get a number with all bits set to 1, i.e., 101 ^ 010 = 111

We can write this fact in the following equation:

number ^ complement = all_bits_set

Let’s add ‘number’ on both sides:

number ^ number ^ complement = number ^ all_bits_set

From the above-mentioned second property:

0 ^ complement = number ^ all_bits_set

From the above-mentioned third property:

complement = number ^ all_bits_set

We can use the above fact to find the complement of any number.

How do we calculate ‘all_bits_set’? One way to calculate all_bits_set will be to first count the bits required to store the given number. We can then use the fact that for a number which is a complete power of ‘2’ i.e., it can be written as pow(2, n), if we subtract ‘1’ from such a number, we get a number which has ‘n’ least significant bits set to ‘1’. For example, ‘4’ which is a complete power of ‘2’, and ‘3’ (which is one less than 4) has a binary representation of ‘11’ i.e., it has ‘2’ least significant bits set to ‘1’.

Code

Here is what our algorithm will look like:

Python3

. . . .

Time Complexity

Time complexity of this solution is O(b) where ‘b’ is the number of bits required to store the given number.

Space Complexity

Space complexity of this solution is O(1).

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible