Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

477. Total Hamming Distance

Time: $O(30n) = O(n)$

Space: $O(1)$

			


class Solution {
 public:
  int totalHammingDistance(vector<int>& nums) {
    int ans = 0;
    int mask = 1;

    for (int i = 0; i < 30; ++i) {
      const int onesCount = count_if(begin(nums), end(nums),
                                     [&mask](int num) { return num & mask; });
      const int zerosCount = nums.size() - onesCount;
      ans += onesCount * zerosCount;
      mask <<= 1;
    }

    return ans;
  }
};




			


class Solution {
  public int totalHammingDistance(int[] nums) {
    int ans = 0;
    int mask = 1;

    for (int i = 0; i < 30; ++i) {
      final int onesCount = getCount(nums, mask);
      final int zerosCount = nums.length - onesCount;
      ans += onesCount * zerosCount;
      mask <<= 1;
    }

    return ans;
  }

  private int getCount(int[] nums, int mask) {
    int count = 0;
    for (final int num : nums)
      if ((num & mask) > 0)
        ++count;
    return count;
  }
}