Solution by prabhavgupta


  • 0
    P

    Approach #1 Brute Force [Accepted]

    Intuition

    Check all the bits if any of them is set to 1, by ANDing itself with 1.

    Algorithm

    We can Loop through all bits in an integer, by using right shift operator. And by doing the bitwise AND operation with 1 and the bit itself we can count the number of set bits.

    C++

    class Solution {
        
    unsigned int CSB(unsigned int n)
    {
      unsigned int count = 0;
        while (n)
        {
    		count += n & 1;
    		n >>= 1;
        }
        return count;
    }
        
    public:
        int hammingDistance(int x, int y) {
            return CSB (x xor y);
        }
    };
    

    Complexity Analysis

    • Time complexity : $$\theta(log(n))$$.

    Approach #2 Brian Kernighan’s Algorithm [Accepted]

    Algorithm

    Step 1 : Subtract 1 from the number . Subtractig a number by 1 , toggles all its bit from right to left till a set bit is reached.

    Step 2 : Now, do a bitwise AND of n with n-1 , this will unset the last set bit in the number.

    Step 3 : Do this untill the number != 0 , and the number of times the loop executes , it will give the required set bit count.

    C++

    class Solution {
        
    unsigned int CSB(unsigned int n)
    {
      unsigned int count = 0;
        while (n)
        {
          n &= (n-1) ;
          count++;
        }
        return count;
    }
        
    public:
        int hammingDistance(int x, int y) {
            return CSB (x xor y);
        }
    };
    

    Complexity Analysis

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

    Approach #3 Using Lookup Table [Accepted]

    Algorithm

    In GCC, the number of set bits can be easily counted using __builtin_popcount().

    C++

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

    Complexity Analysis

    • Time complexity : $$O(1)$$

Log in to reply
 

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