8-lines DP solution by one pass with explanation


  • 2
    J

    It's really a straight forward method. To sum the distances of every pair, you can make it with element one by one. For example, you check first element and second one, then check the coming third one with first and second element as: (1,2), (1,3), (2,3)...So the only thing you need to do is check how many more distances come with a new element nums[k] with passed elements nums[0],nums[1],...,nums[k-1].

    I used a matrix(O(1) space) to store total amounts of 0's and 1's at every bit of already passed numbers.
    (x>>i)&1 gets the ith bit of current number.
    ((x>>i)&1)^1 gets the opposite of ith bit of current number, which makes the total Hamming distances between current number and passed numbers.

        public int totalHammingDistance(int[] nums) {
            int[][] dp = new int[31][2];
            int res = 0;
            for (int x : nums)
                for (int i=0; i<31; ++i) {
                    ++dp[i][(x>>i)&1];
                    res += dp[i][((x>>i)&1)^1];
                }
            return res;
        }
    

  • 0

    @daozhuang It would be great if you could explain more~


  • 2
    J

    @BryanBo.Cao It's really a straight forward method. To sum the distances of every pair, you can make it with element one by one. For example, you check first element and second one, then check the coming third one with first and second element as: (1,2), (1,3), (2,3)...So the only thing you need to do is check how many more distances come with a new element nums[k] with passed elements nums[0],nums[1],...,nums[k-1].


Log in to reply
 

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