Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Complement of Base 10 Number (medium)

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.

.....

.....

.....

Like the course? Get enrolled and start learning!
J

J

· 4 years ago

Python3 solution's 3rd line should be bit_count, n = 0, num. It also fails for test case num = 0 unless you include an if statement for that edge case i.e. adding the line if num == 0: return 1 before line 3.

Show 1 reply
A

Adam Sweeney

· 4 years ago

The pow() function in C++ is exclusive to floating point types. You'd be better off with a small function that does proper integer multiplication.

Show 1 reply
J

Joey

· 4 years ago

Any reason why we can’t just do

numberOfBits = int(math.floor(math.log2(number)) + 1)

?

What would be the impact of complexity in this case? Since we’re not dealing with an array but number of bits

Show 2 replies
B

Baraa Attabbaa

· 3 years ago

all_bits_set = 2 ** (math.ceil(math.log2(num)) + 1) - 1
Arturo Calderón

Arturo Calderón

· 3 years ago

def GetComplement(num):
    mask = 1
    while mask < num:
        mask = mask << 1
        mask += 1
    return mask ^ 1
Miguel

Miguel

· 2 years ago

Adding this here in a case a slightly different approach clicks for someone. The basic idea is that when you xor a bit with 1, you get the compliment (0^1 = 1; 1^1 = 0). To take advantage of this, we apply XOR to every bit of number to get the total complement:

import math

class Solution:
  def bitwiseComplement(self, num):
    # Idea: xor every bit of num with 1

    complement = 0
    place_bit = 1 #start at place 1
    places = math.ceil(math.log2(num)) # determine number of bits in num

    for _ in range(places):
      num_at_place_bit = place_bit & num #gives you the num's bit at the place_bit bit
      complement |= num_at_place_bit ^ place_bit #xor-ing with 1 gives you the complimentary bit; |= accumulates the result with previous results
      place_bi
Show 1 reply