Compute the Total Hamming Distance between All Pairs of Integers
- 时间:2020-09-18 17:01:02
- 分类:网络文摘
- 阅读:91 次
The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Now your job is to find the total Hamming distance between all pairs of the given numbers.
Example:
Input: 4, 14, 2Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.Note:
Elements of the given array are in the range of 0 to 10^9
Length of the array will not exceed 10^4.
Bruteforce Algorithm to Compute the Hamming distances between Pairs of Integers
We need O(N^2) to iterate over each possible pair of integers, then we can add up the hamming distance with O(logV) complexity. The overall complexity is O(N^2LogV). We can use the std::bitset to perform the counting the set bits.
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution { public: int totalHammingDistance(vector<int>& nums) { int ans = 0; for (int i = 0; i < nums.size(); ++ i) { for (int j = i + 1; j < nums.size(); ++ j) { int t = nums[i] ^ nums[j]; ans += bitset<32>(t).count(); } } return ans; } }; |
class Solution { public: int totalHammingDistance(vector<int>& nums) { int ans = 0; for (int i = 0; i < nums.size(); ++ i) { for (int j = i + 1; j < nums.size(); ++ j) { int t = nums[i] ^ nums[j]; ans += bitset<32>(t).count(); } } return ans; } };
Alternatively, we can use the compiler intrinsic i.e. __builtin_popcount to achieve the same task.
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution { public: int totalHammingDistance(vector<int>& nums) { int ans = 0; for (int i = 0; i < nums.size(); ++ i) { for (int j = i + 1; j < nums.size(); ++ j) { int t = nums[i] ^ nums[j]; ans += __builtin_popcount(t); } } return ans; } }; |
class Solution { public: int totalHammingDistance(vector<int>& nums) { int ans = 0; for (int i = 0; i < nums.size(); ++ i) { for (int j = i + 1; j < nums.size(); ++ j) { int t = nums[i] ^ nums[j]; ans += __builtin_popcount(t); } } return ans; } };
Iterating the Bits and Perform the Math Counting
As the integers are 32-bit. We can iterate each number, and each bit to count the set bits. Suppose there are n integers, and for a bit, there are k set bits. Thus the overall hamming distances for this bit would have to be k * (n – k). The Hamming distance will be the sum of the XOR bits, thus the combinations between the 1’s and 0’s in the binary representation.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | class Solution { public: int totalHammingDistance(vector<int>& nums) { if (nums.empty()) return 0; int k = nums.size(); int bits[32]; std::fill(begin(bits), end(bits), 0); for (auto &n: nums) { int i = 0; while (n > 0) { bits[i ++] += n & 0x1; n >>= 1; } } int ans = 0; for (const auto &n: bits) { ans += n * (k - n); } return ans; } }; |
class Solution { public: int totalHammingDistance(vector<int>& nums) { if (nums.empty()) return 0; int k = nums.size(); int bits[32]; std::fill(begin(bits), end(bits), 0); for (auto &n: nums) { int i = 0; while (n > 0) { bits[i ++] += n & 0x1; n >>= 1; } } int ans = 0; for (const auto &n: bits) { ans += n * (k - n); } return ans; } };
The overall complexity is O(N logV). And the space requirement is O(1) constant.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:甲校二队已赛了几场 这类自然数共有多少个 网站吸引蜘蛛抓取的方法 谷歌白帽SEO如何在黑帽SEO的夹击中突围? 网站权重从0到1的方法 SEO优化具体怎么操作? 百度图片搜索怎么优化、收录、排名和免费引流? 你有搜索引擎优化面试的技巧吗? Google谷歌SEO排名的5个因素 搜索引擎优化如何内容建设
- 评论列表
-
- 添加评论