Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Complement of Base 10 Number (medium)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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
A

Anonymous

· 3 years ago

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

Anonymous

· 3 years ago

all_bits_set = 2 ** (math.ceil(math.log2(num)) + 1) - 1
A

Anonymous

· 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

Anonymous

· 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
A

Anonymous

· 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

Reading Progress

0%

Vote for new content