C++ में कुल हैमिंग दूरी (Total Hamming Distance)

समस्या विवरण

संख्याओं की एक सूची दी गई है। हमें सभी जोड़ों (pairs) की हैमिंग दूरी (Hamming distance) का योग ज्ञात करना है। दो पूर्णांकों के बीच हैमिंग दूरी उन बिट स्थितियों की संख्या है जहां संबंधित बिट्स भिन्न होते हैं।

उदाहरण

इनपुट

[4, 14, 17, 2]

आउटपुट

17

समाधान दृष्टिकोण (बिट मैनिपुलेशन)

प्रत्येक बिट स्थिति (0 से 31) के लिए स्वतंत्र रूप से गणना करें:

• उस बिट पर सेट बिट्स (1s) की संख्या गिनें: count1
• अनसेट बिट्स (0s) की संख्या: count0 = n - count1
• उस बिट का कुल योगदान: count1 × count0
• सभी 32 बिट्स के लिए योग करें।

समय जटिलता: O(32 × n) = O(n)

कार्यकारी प्रोग्राम

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

class Solution {
public:
    lli add(lli a, lli b) { return ((a % MOD) + (b % MOD)) % MOD; }
    lli mul(lli a, lli b) { return ((a % MOD) * (b % MOD)) % MOD; }
    
    int totalHammingDistance(vector<int>& nums) {
        vector<vector<lli>> bits(32, vector<lli>(2, 0));
        lli ans = 0;
        int n = nums.size();
        
        for (int i = 0; i < n; i++) {
            lli x = nums[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 main() {
    Solution ob;
    vector<int> v = {4, 14, 17, 2};
    cout << ob.totalHammingDistance(v);
    return 0;
}

आउटपुट

17