Easy to under stand java solution, bit manipulation.


  • 0
    F

    Key word: Hamming distance, Array of numbers, Hamming distance between each pair.
    Requirement: Find the total hamming distance.
    Brute force: For each pair of number, calculate their hamming distance, Time complexity is O(n^2).
    Improved method:

    1. Vertically take a look at the bits at a given position across all the numbers.
    2. Every bit is either one or zero, let`s say we have x set bits and y unset bits, the total pairs that can generate a distance of 1 at this position is x*y.
    3. Apply the above calculation to all bits and sum up the total distance.
    4. Time complexity is O(n) and space complexity is O(1).
    public class Solution {
        public int totalHammingDistance(int[] nums) {
            int total = 0;
            int mask = 1;
            for (int i = 0; i < 32; i++) {
                int setBit = 0;
                for (int j : nums) {
                    setBit += (j & mask) == 0 ? 0 : 1;
                }
                total += setBit * (nums.length - setBit);
                mask <<= 1;
            }
            return total;
        }
    }
    

Log in to reply
 

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