Total Hamming Distance

https://leetcode.com/problems/total-hamming-distance/description/

O(n)

public int totalHammingDistance(int[] nums) {
    int total = 0, n = nums.length;
    for (int j=0;j<32;j++) {
        int bitCount = 0;
        for (int i=0;i<n;i++) 
            bitCount += (nums[i] >> j) & 1;
        total += bitCount*(n - bitCount);
    }
    return total;
}

O(n^2) time limit error

class Solution {
    public int totalHammingDistance(int[] nums) {
        int res = 0;
        for(int i = 0; i < nums.length - 1; i++){
            for(int j = i + 1; j < nums.length; j++){
                res += compareTwoBits(nums[i], nums[j]);
            }
        }

        return res;
    }

    private int compareTwoBits(int n1, int n2){
        int num = 0;
        for(int i = 0; i < 32; i++){
            num += ((n1 >> i) & 1) == ((n2 >> i) & 1)? 0 : 1;
        }

        return num;
    }
}

results matching ""

    No results matching ""