C++ solution with little hit| O(n), bitwise

  • 0

    Compared to calculate every pair of numbers, processing with every digit from all numbers is clever.
    Since Hamming distance will be added when two numbers are different, this problem turn to be "counting the number of cases that pari numbers are different in every digit."
    So for binary numbers, what we should do is counting how many 1 existing in this digit, and count(0) = nums.size() - count(1)
    Then different pairs exists when two numbers are from different sets that total += count(1) * count(0).

    class Solution {
        int totalHammingDistance(vector<int>& nums) {
            int ans = 0, ns, t = 0;
            if (nums.size()<2) return 0;        
            while (t < nums.size()){
                ns = 0;
                t = 0;
                for (int i =0; i < nums.size(); i++){
                    //caculate from the last digit
                    ns += nums[i]&1;
                    nums[i] = nums[i] >> 1;
                    if (nums[i]==0) t++;
                ans += ns * (nums.size()-ns);
            return ans;

Log in to reply

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