Giả sử chúng ta có một danh sách các số. Chúng ta phải tìm khoảng cách Hamming của tất cả các cặp số cho trước. Chúng ta biết rằng khoảng cách Hamming giữa hai số nguyên là số vị trí mà các bit tương ứng khác nhau.
Vì vậy, nếu đầu vào giống như [4,14,17,2], thì đầu ra sẽ là 17.
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −
m := 1^9 + 7
Định nghĩa hàm add(), nhận a, b,
trả về ((a mod m) + (b mod m))
Định nghĩa hàm mul(), nhận a, b,
trả về ((a mod m) * (b mod m))
Định nghĩa hàm cntBits(), nhận mảng a,
Định nghĩa mảng 2D bits kích thước 32 x 2
ans := 0, n := kích thước của a
for khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), thực hiện −
x := a[i]
for khởi tạo j := 0, khi j < 32, cập nhật (tăng j lên 1), thực hiện −
b := (x / 2^j) AND 1
ans := add(ans, mul(1, bits[j, inverse of b]))
bits[j, b] := add(bits[j, b], 1)
trả về ans
Từ phương thức main thực hiện như sau −
trả về cntBits(nums)
Hãy xem triển khai sau để hiểu rõ hơn −
Ví dụ
#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)); } Đầu vào
{4,14,17,2} Đầu ra
17