C++-এ মোট হ্যামিং দূরত্ব (Total Hamming Distance) গণনা

একটি সংখ্যা লিস্ট দেওয়া থাকলে, সব যুগল সংখ্যার হ্যামিং দূরত্বের যোগফল বের করতে হবে। দুটি পূর্ণসংখ্যার হ্যামিং দূরত্ব হলো তাদের বাইনারি রিপ্রেজেন্টেশনে পার্থক্যপূর্ণ বিটের সংখ্যা।

উদাহরণ

ইনপুট: [4, 14, 17, 2] → আউটপুট: 17

সমাধানের ধাপসমূহ

প্রতিটি বিট পজিশন (০ থেকে ৩১) এর জন্য আলাদা আলাদা গণনা করুন।
প্রতিটি সংখ্যার জন্য, ওই বিট পজিশনে ১ আছে কিনা চেক করুন।
যে সংখ্যাগুলোতে ১ আছে তাদের সংখ্যা count1, যেগুলোতে ০ আছে তাদের count0 = n - count1।
ওই বিটের জন্য হ্যামিং দূরত্বের অবদান = count1 * count0।
সকল বিটের যোগফল নিন।

প্রোগ্রাম উদাহরণ

#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)) % m;
    }
    
    lli mul(lli a, lli b) {
        return ((a % m) * (b % m)) % 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(1, bits[j][!b]));
                bits[j][b] = add(bits[j][b], 1);
            }
        }
        return ans;
    }
    
    int totalHammingDistance(vector<int>& nums) {
        return cntBits(nums);
    }
};

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

ইনপুট

{4, 14, 17, 2}