ระยะทางแฮมมิงรวมใน C++

ให้รายการตัวเลข งานคือหาระยะทางแฮมมิง (Hamming distance) ของทุกคู่ของตัวเลขที่กำหนด ระยะทางแฮมมิงระหว่างสองจำนวนเต็มคือจำนวนตำแหน่งบิตที่ต่างกัน

เช่น [4,14,17,2] เอาต์พุตคือ 17

วิธีแก้ − นับบิต 1 และ 0 ในแต่ละตำแหน่งของทุกตัวเลข คำนวณจำนวนคู่ที่บิตต่างกัน

ตัวอย่าง

#include <bits/stdc++.h> 
using namespace std; 
typedef long long int lli; 
const int m = 1e9 + 7; 

class Solution { 
public: 
    lli add(lli a, lli b){ return ((a % m) + (b % m)); } 
    lli mul(lli a, lli b){ return ((a % m) * (b % m)); } 
    int cntBits(vector<int>& a){ 
        vector<vector<lli> > bits(32, vector<lli>(2)); 
        lli ans = 0; int n = a.size(); 
        for (int i = 0; i < n; i++) { 
            lli x = a[i]; 
            for (lli j = 0; j < 32; j++) { 
                lli b = (x >> j) & 1; 
                ans = add(ans, mul((lli)1, bits[j][!b])); 
                bits[j][b] = add(bits[j][b], (lli)1); 
            } 
        } 
        return ans; 
    } 
    int totalHammingDistance(vector<int>& nums){ return cntBits(nums); } 
}; 

main(){ 
    Solution ob; 
    vector<int> v = {4,14,17,2}; 
    cout << (ob.totalHammingDistance(v)); 
}

อินพุต

{4,14,17,2}