ระยะทางรวมใน 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() ซึ่งจะใช้อาร์เรย์ a,

• กำหนดบิตอาร์เรย์ 2 มิติขนาด 32 x 2 หนึ่งบิต

• ans :=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]))

    • บิต[j, b] :=add(บิต[j, b], 1)

• กลับมาอีกครั้ง

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• คืนค่า cntBits(nums)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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