Solution by Ambition_Wang


  • 1
    A

    Approach #1 Converting data type [Accepted]

    Algorithm

    1. convert x, y to binary representation with string type
    2. (optional) filled with leading zeros
    3. compare each bit one by one

    Python

    def hammingDistance(self, x, y):
        # convert decimal+integer to binary+string
        y_bin_str = self.dec_to_bin(y)
        x_bin_str = self.dec_to_bin(x)
        # filled with leading zeros
        while len(y_bin_str) != len(x_bin_str):
            if len(y_bin_str) < len(x_bin_str):
                y_bin_str = '0' + y_bin_str
            elif len(y_bin_str) > len(x_bin_str):
                x_bin_str = '0' + x_bin_str
        # compare different bits
        dif_bit_num = 0
        for i in range(len(x_bin_str)):
            if x_bin_str[i] != y_bin_str[i]:
                dif_bit_num += 1
        return dif_bit_num
    
    def dec_to_bin(self, i):
        if i == 0:
            return '0'
        i_str = ''
        while i > 0:
            if i % 2 == 1:
                i_str = '1' + i_str
            else:
                i_str = '0' + i_str
            i = int(i / 2)
        return i_str
    

    2 common way to convert decimal-integer to binary-string

    % 2: get least significant bit

    • Current quotient becomes next dividend
    • When current quotient is equal to zero, ends it
    • Take remainder from the bottom to the top

    e.g. 5

    1. 5 / 2 = 2...1
    2. 2 / 2 = 1...0
    3. 1 / 2 = 0...1

    Take remainder from the bottom to the top: 101

    e.g. 4

    1. 4 / 2 = 2...0
    2. 2 / 2 = 1...0
    3. 1 / 2 = 0...1

    Take remainder from the bottom to the top: 100

    def dec_to_bin(i):
        if i == 0:
            return "0"
        s = ''
        while i > 0:
            if i % 2 == 1:
                s = '1' + s
            else:
                s = '0' + s
            i = int(i / 2)
        return s
    

    & 1: check least significant bit is 1 or 0, because when least significant bit is 0, it means this number is power of 2

    e.g. 4 (100)

    4 & 1 = 100 & 001 = 000

    e.g. 3 (11)

    3 & 1 = 11 & 01 = 01

    def dec_to_bin(i):
        if i == 0:
            return "0"
        s = ''
        while i > 0:
            if i & 1 == 1:
                s = "1" + s
            else:
                s = "0" + s
            i = int(i/2)
        return s
    

    2 advanced way to convert decimal-integer to binary-string

    Convert to other positional numeral system and concatenate together

    1. convert to octal string prefixed with '0o'
      • oct can convert integer to octal representation with string type
      • [2:] create new string without prefix '0o'
    2. according to decimal number to concatenate proper octal string
    def dec_to_bin(i):
        s = ''
        dec_to_oct = {'0': '000', '1': '001', '2': '010', '3': '011', '4': '100', '5': '101', '6': '110', '7': '111'}
        for bit in oct(i)[2:]:
            s += dec_to_oct[bit]
        return s
    

    Recursion

    Base case:

    If it only contains one bit, just return it

    Recursive case:

    • i & 1: get least significant bit of i
      • 101 & 1 = 001 = 1
      • 100 & 1 = 000 = 0
    • i >> 1: (shift bits to right) proceed to next least significant bit of i
      • 110 >> 1 = 11
      • 100 >> 1 = 10
    1. Plus least significant bit of i
    2. make recursive call with shifting bits to right so that we can proceed to the next least significant bit
    def dec_to_bin(i):
        return str(i) if i <= 1 else dec_to_bin(i >> 1) + str(i & 1)
    

    e.g. 5 (101)

    1. 5 > 1, calls f(2) + '1'
    2. (2): 2 > 1, calls f(1) + '0'
    3. f(1): 1 <= 1, return '1'

    e.g. 6 (110)

    1. 6 > 1, calls f(3) + '0'
    2. f(3): 3 > 1, calls f(1) + '1'
    3. f(1): 1 <= 1, return '1'

    Complexity Analysis

    • Time complexity : $$O(n)$$.
    • dec_to_bin is $$O(n)$$
      • it needs to iterate through whole bits: $$O(len(x)) = O(n)$$
    • filling leading zeros is $$O(|len(x)-len(y)|)$$
    • for loop used to compare is $$O(len(x)) = O(n)$$
    • Space complexity : $$O(n)$$.

    x_bin_str, y_bin_str are both $$O(n)$$


    Approach #2 Bit Manipulate [Accepted]

    Intuition

    To find out how many different bit, we can simply do xor and calculate how many number of bits is 1.

    Algorithm

    1. XOR x and y
    2. get how many number of bits is 1

    Python

    def hammingDistance(self, x, y):
        # XOR x and y
        x_xor_y = x ^ y
        # calculate how many number of bits are 1
        return self.get_ones_count(x_xor_y)
    
    def get_total_ones(self, n):
        '''
        every time you perform the operation n & (n-1), a single 1 bit is erased
        '''
        total = 0
        while n != 0:
            n = n & (n - 1)
            total += 1
        return total
    

    3 common way to calculate how many number of bits are 1?

    iterate through loop with string type

    total = 0
    for i in range(len(bin_str)):
        if bin_str[i] == 1:
            total += 1
    return total
    

    & 1: check wether least significant bit is 1 each time

    • e.g. 5 (101)

    101 & 1 = 101 & 001 = 1 (least significant bit is 1)

    • e.g. 4 (100)

    100 & 1 = 100 & 001 = 0 (least significant bit is not 1)

    total = 0
    while num != 0:
        if num & 1 == 1:
            total += 1
        num = num >> 1  # shift right to get next least significant bit
    return total
    

    n & (n-1): remove a single 1 bit each time

    http://graphics.stanford.edu/~seander/bithacks.html

    Least significant 1 bit of x will not on the original position after being subtracted by 1, so AND both number causes this position to be zero

    • e.g. xxxx10 (x is 1 or 0 doesn't matter because subtracting 1 only affect least significant 1 bit)

    xxxx10 & xxxx01 = xxxx00 (Least significant 1 bit is removed)

    • e.g. xxxx01

    xxxx01 & xxxx00 = xxxx00 (Least significant 1 bit is removed)

    • e.g. xxxx11

    xxxx11 & xxxx10 = xxxx10 (Least significant 1 bit is removed)

    total = 0
    while num != 0:
        num = num & (num-1)
        total += 1
    return total
    

    Complexity Analysis

    • Time complexity : $$O(n)$$.

    You needs both bits of x and y to be compared, so time complexity is $$O(length of bits) = O(n)$$

    • Space complexity : $$O(n)$$.

    x_xor_y is $$O(n)$$, although it can be avoided.


    Approach #3 Built-in function

    Java

    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
    

    Python

    def hammingDistance(self, x, y):
        return bin(x^y).count('1')
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.