मान लीजिए हमारे पास संख्याओं की एक सूची है। हमें दी गई संख्याओं के सभी युग्मों की हैमिंग दूरी ज्ञात करनी है। हम जानते हैं कि दो पूर्णांकों के बीच हैमिंग की दूरी उन स्थितियों की संख्या है, जिन पर संगत बिट भिन्न होते हैं।
तो, अगर इनपुट [4,14,17,2] जैसा है, तो आउटपुट 17 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
मी :=1^9 + 7
-
फ़ंक्शन ऐड () को परिभाषित करें, इसमें a, b,
. लगेगा -
वापसी ((एक मॉड एम) + (बी मॉड एम))
-
फ़ंक्शन mul() को परिभाषित करें, इसमें a, b,
. लगेगा -
वापसी ((एक मॉड एम) * (बी मॉड एम))
-
फ़ंक्शन को परिभाषित करें cntBits(), यह एक सरणी लेगा,
-
32 x 2 आकार के एक 2D सरणी बिट्स को परिभाषित करें
-
उत्तर:=0, n:=आकार एक
-
इनिशियलाइज़ i:=0 के लिए, जब i
-
एक्स:=ए[i]
-
इनिशियलाइज़ j :=0 के लिए, जब j <32, अपडेट करें (j को 1 से बढ़ाएँ), करें -
-
बी:=(एक्स / 2^जे) और 1
-
Ans :=add(ans, mul(1, bit[j, inverse of b]))
-
बिट्स [जे, बी]:=जोड़ें (बिट्स [जे, बी], 1)
-
-
-
वापसी उत्तर
-
मुख्य विधि से निम्न कार्य करें -
-
वापसी cntBits(अंक)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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} आउटपुट
17