This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

2. How to solve the problem

Leetcode is a question of the day. Today is an updated version of hamming distance. Yesterday we learned how to calculate the Hamming distance

1. Bit-by-bit statistics

If we compute the Hamming distance of a pair of numbers in pairs, the time complexity is O(n^2logn). Is there a less complex algorithm? The answer is yes:

For an element val in the array NUMs, if the ith bit of its binary is 1, we only need to count how many elements in NUMS have the ith bit of 0, that is, we calculate the sum of the Hamming distances of val and other elements at the ith bit. In particular, if the ith bit of all elements in the binary of nums has c ones and N āˆ’ C zeros, the sum of the Hamming distances of the elements in the ith bit of the binary is c (nāˆ’ C).Copy the code

Code implementation

class Solution { public int totalHammingDistance(int[] nums) { int ans = 0, n = nums.length; for (int i = 0; i < 30; ++i) { int c = 0; for (int val : nums) { c += (val >> i) & 1; } ans += c * (n - c); } return ans; }}Copy the code

Time complexity analysis

Only bits 1 of N numbers need to be counted, so the time complexity is:

  • O (n ā‹… L) with L = 30

Spatial complexity analysis

Constant auxiliary space, so space complexity:

  • O(1)

I don’t know if I have made myself clear, please give me more advice. Punch out for the day!