[bit manipulation]477. Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:
Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Note:
Elements of the given array are in the range of 0 to 10^9
Length of the array will not exceed 10^4.

Brute force: time limit exceed
思路:integer一共32位, int[] count = new int[32]记录每个bit一共在几个数字中on(一共n = nums.length个数字)。对于一个bit,on的次数 k 次,off的次数 n-k 次,则对于total distance的贡献是 k * (n-k),因为每一个(on, off)的组合都会给total distance加1.

    public int totalHammingDistance(int[] nums) {
        int N = nums.length;
        int[] count = new int[32]; // count for when the bit is on
        for (int n : nums) {
            int i = 0;
            while (n > 0) {
                count[i++] += n & 1;
                n >>= 1;
            }
        }
        
        int total = 0;
        for (int i = 0; i < 32; i++) {
            total += count[i] * (N - count[i]);
        }
        return total;
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s