C++ এ মোট হ্যামিং দূরত্ব

ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে। আমাদের প্রদত্ত সংখ্যার সমস্ত জোড়ার হ্যামিং দূরত্ব খুঁজে বের করতে হবে। আমরা জানি যে দুটি পূর্ণসংখ্যার মধ্যে হ্যামিং দূরত্ব হল অবস্থানের সংখ্যা যেখানে সংশ্লিষ্ট বিটগুলি আলাদা।

সুতরাং, ইনপুট যদি [4,14,17,2] এর মত হয়, তাহলে আউটপুট হবে 17।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• মি :=1^9 + 7

• একটি ফাংশন add() সংজ্ঞায়িত করুন, এটি a, b,

  লাগবে

• ফিরুন ((a mod m) + (b mod m))

• একটি ফাংশন mul() সংজ্ঞায়িত করুন, এটি a, b,

  লাগবে

• (a mod m) * (b mod m))

  ফেরত দিন

• একটি ফাংশন সংজ্ঞায়িত করুন cntBits(), এটি একটি অ্যারে নেবে,

• 32 x 2 আকারের একটি 2D অ্যারে বিট সংজ্ঞায়িত করুন

• উত্তর :=0, n :=a

  এর আকার

• আরম্ভ করার জন্য i :=0, যখন i

  • x :=a[i]

  • j শুরু করার জন্য :=0, যখন j <32, আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), −

    করুন

    • b :=(x / 2^j) এবং 1

    • ans :=add(ans, mul(1, bits[j, inverse of b]))

    • বিটস[জে, বি] :=অ্যাড(বিটস[জে, বি], ১)

• উত্তর ফেরত দিন

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• 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