Solution by Na2a


  • 2
    A

    First idea that comes to mind is to take all positions and check if bits
    at corresponding positions are different.

    Approach 1. Naive

    Intuition:
    Given two numbers A and B. We can take the lowest bit of A and the lowest bit of B
    and check if they are equal. Then, we just delete these two bits.

    Getting the lowest bit:
    If we represent a number in binary system, we will have sum of some powers of two.
    For example, let's consider 22. It's binary representation is 10110, so
    22 = 12^4 + 02^3 + 12^2 + 12^1 + 0*2^1. As you can see, the lowest bit of any
    number defines a parity of this number. That is, odd numbers will have 1 as the lowest bit,
    even numbers will have 0.

    Removing the lowest bits:
    Let's take 22 again. It's binary representation is 10110. Now, let's remove last
    (lowest) bit. It becomes 1011 which is 11. Here's the trick: removing the
    lowest bit is same as diving by 2. If number is odd, just round it down, so 23
    without the last bit is also 11.

    Algorithm: While either of number is positive, just take the lowest bits,
    compare them until we will finish with all positions.

    class Solution {
    public:
        // getting the lowest bit
        int getLowestBit(int x) {
            return x % 2;
        }
        int removeLowestBit(int x) {
            return x / 2;
        }
        int hammingDistance(int x, int y) {
            int result = 0;
            while (x > 0 or y > 0) {
                int bit_x = getLowestBit(x);
                int bit_y = getLowestBit(y);
                if (bit_x != bit_y)
                    result++;
                x = removeLowestBit(x);
                y = removeLowestBit(y);
            }
            return result;
        }
    };
    

    Complexity Analysis:
    Time complexity: O(log2(max(A, B))).

    If we can just iterate through all
    positions (bits), this should work in $$O(numberOfPositions)$$. And we know that
    decimal number N will have O(log2(N)) bits in binary representation. So solution
    will be O(log(max(A, B))).

    Approach 2. Bit operations

    Intuition:
    What does the XOR operation do? For each position in binary representation,
    A xor B will have 1 if bits in corresponding positions differ. That's what we need.
    Answer for this problem will be number of ones in A xor B.

    Algorithm: Just find A xor B and count number of bits in it. In C++, that
    would be pretty short.

    class Solution {
    public:
        int hammingDistance(int x, int y) {
            return __builtin_popcount(x ^ y);
        }
    };
    

    Complexity Analysis:
    Time complexity: O(log2(max(A, B))).
    XOR operation works in O(1), although counting number of ones will be O(log2(N)).


Log in to reply
 

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