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

Topic describes

The Hamming distance of two integers refers to the number of different bits corresponding to the binary number of the two numbers.

Calculates the sum of the Hamming distances between any two numbers in an array.

Example: input: 4, 14, 2 output: 6 description: in binary representation, 4 is 0100,14 is 1110, and 2 is 0010. HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6 Source: LeetCode Link: https://leetcode-cn.com/problems/total-hamming-distance Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Train of thought

• Today’s problem is an upgraded version of hamming distance. After analyzing the problem, it can be divided into two sub-problems.
• Subproblem one is finding a subset of length two.
• Subproblem two is to find the Hamming distance of a subset. The following code can be obtained:

code

public int totalHammingDistance(int[] nums) {
        int ans = 0;
        List<List<Integer>> subLists = subList(nums);
        for (List<Integer> item : subLists) {
            if (item.size() == 2) {
                ans += Integer.bitCount(item.get(0) ^ item.get(1)); }}return ans;
    }

    public List<List<Integer>> subList(int[] nums) {
        List<List<Integer>> subLists = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        dfs(nums, 0, temp, subLists);
        return subLists;
    }

    private void dfs(int[] nums, int level, List<Integer> temp, List<List<Integer>> subLists) {
        if (level == nums.length) {
            subLists.add(new ArrayList<>(temp));
            return;
        }
        dfs(nums, level + 1, temp, subLists);
        temp.add(nums[level]);
        dfs(nums, level + 1, temp, subLists);
        temp.remove(temp.size() - 1);
    }
Copy the code

• The above code first solves all the subsets of NUMs, and then takes the subsets of length 2 to find the sum of hamming distances. Submission timeout failed!
• After the submission timeout, the problem was analyzed again and it was found that there was no need to enumerate all the subsets, only the subset of length 2 was needed. The optimized code is as follows:

    public int totalHammingDistance1(int[] nums) {
        int ans = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) { ans += Integer.bitCount(nums[i] ^ nums[j]); }}return ans;
    }
Copy the code

Submit tests:

• This code is AC, but the time complexity is O (n * N), and there is still room for optimization.
• Refer to the official solution to obtain the following code. The core idea of this method is to count the number of bits 1 and 0 respectively, and then calculate the global Hamming distance. It’s not an easy idea to think of. Learning a new idea!

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

Submit tests:

conclusion

• This topic has been submitted for many times before it was approved. I took some detours in my thinking. The paper come zhongjue shallow, must know this to practice! Or to seriously analyze the topic, sorting out ideas, and constantly improve!
• Stick to the daily question, come on!