Leetcode|Leetcode | Hamming Distance Leetcode|leetcode

461. Hamming Distance

class Solution { public: int hammingDistance(int x, int y) { /* // caculate from first digit int n = x ^ y, ns = 0; while (n) { ++ ns; n &= n - 1; } */ // caculate from last digit int n = x ^ y, ns = 0; while (n){ ns += n & 1; n = n >> 1; } return ns; } };

3ms/E
477. Total Hamming Distance

C++ solution with little hit| O(n), bitwise
- Compared to calculate every pair of numbers, processing with every digit from all numbers is clever.
- Since Hamming distance will be added when two numbers are different, this problem turn to be “counting the number of cases that pari numbers are different in every digit.”
- So for binary numbers, what we should do is counting how many 1 existing in this digit, and count(0) = nums.size() - count(1).
- Then different pairs exists when two numbers are from different sets that total += count(1) * count(0).

class Solution { public: int totalHammingDistance(vector& nums) { int ans = 0, ns, t = 0; if (nums.size()<2) return 0; while (t < nums.size()){ ns = 0; t = 0; for (int i =0; i < nums.size(); i++){ //caculate from the last digit ns += nums[i]&1; nums[i] = nums[i] >> 1; if (nums[i]==0) t++; } ans += ns * (nums.size()-ns); } return ans; } };

【Leetcode|Leetcode | Hamming Distance】59ms/M