online advertising

Monday, February 20, 2017

LeetCode OJ - Total Hamming Distance

Problem:

Please find the problem here.

Analysis:

The input could have 10,000 elements, we need to figure out a way to compute the total hamming distance without going through all pairs.

Solution:

Imagine for a bit they are all 1 bit number (i.e. either 0 or 1), then it is easy. Just count the number of zeros and number of ones and multiply them together.

For a full solution, just do this for all bits.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/total-hamming-distance

#include "LEET_TOTAL_HAMMING_DISTANCE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_TOTAL_HAMMING_DISTANCE
{
    class Solution
    {
    public:
        int totalHammingDistance(vector<int>& nums)
        {
            int dist = 0;
            int mask = 1;
            for (int i = 0; i < 32; i++)
            {
                int zero = 0;
                int ones = 0;
                for (size_t j = 0; j < nums.size(); j++)
                {
                    bool is_zero = (nums[j] & mask) == 0;
                    if (is_zero) { zero++; } else { ones++; }
                }
                dist += zero * ones;
                mask = mask << 1;
            }
            return dist;
        }
    };
};

using namespace _LEET_TOTAL_HAMMING_DISTANCE;

int LEET_TOTAL_HAMMING_DISTANCE()
{
    Solution solution;
    int input_array[] = { 4, 14, 2 };
    vector<int> input(input_array, input_array + _countof(input_array));
    cout << solution.totalHammingDistance(input) << endl;
    return 0;
}

No comments :

Post a Comment