LeetCode 477 - Total Hamming Distance

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

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, 2

Output: 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:

1. Elements of the given array are in the range of 0 to 10^9
2. Length of the array will not exceed 10^4.

X. Bit Counting
https://leetcode.com/problems/total-hamming-distance/discuss/96226/java-on-time-o1-space

For each bit position 1-32 in a 32-bit integer, we count the number of integers in the array which have that bit set. Then, if there are n integers in the array and k of them have a particular bit set and (n-k) do not, then that bit contributes k*(n-k) hamming distance to the total.

public int totalHammingDistance(int[] nums) {
    int total = 0, n = nums.length;
    for (int j=0;j<32;j++) {
        int bitCount = 0;
        for (int i=0;i<n;i++) 
            bitCount += (nums[i] >> j) & 1;
        total += bitCount*(n - bitCount);
    }
    return total;
}

https://zyfu0408.gitbooks.io/interview-preparation/content/bit-manipulation/bit.html
这题brute force的做法是两重for循环，用上一题的方法，两两比较，O(n ^ 2)的时间复杂度，超时了。

O(n)的复杂度的做法是，外层的for循环遍历int上的每一位，内层的for循环遍历数组，统计每一位出现了1的count，那该位的hamming distance就是count * (array.length - count)。

    public int totalHammingDistance(int[] nums) {
        int total = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num: nums) {
                if ((num >> i & 1) == 1) {
                    count++;
                }
            }
            total += count * (nums.length - count);
        }
        return total;
    }

    public int hammingDistance(int x, int y) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            int n1 = x >> i & 1;
            int n2 = y >> i & 1;
            if (n1 != n2) {
                count++;
            }
        }
        return count;
    }

http://startleetcode.blogspot.com/2016/12/477-total-hamming-distance.html
May use the bitwise operation to reduce the time complexity. All the numbers can be viewed as 32 bits with 0s and 1s. So for each bit, we just need to count the total number of 1s, then the total number of 0s will be (total numbers - the numbers of 1s). And the contribution to the Hamming distance will be count of 1s times the count of 0s. Similarly argument can be applied to all the rest bits.

1.     int totalHammingDistance(vector<int>& nums) {
2.         int res = 0;
3.         for(int i=0; i<32; ++i){
4.             int one = 0;
5.             for(int j=0; j<nums.size(); ++j){
6.                 if((1<<i) & nums[j]) ++one;//one is the numbers of 1s;
7.             }
8.             res += one*(nums.size()-one);// nums of 1s x nums of 0s
9.         }
10.         return res;
11.     }

http://bookshadow.com/weblog/2016/12/18/leetcode-total-hamming-distance/

按位统计各整数的二进制0与1的个数之和，分别记为zero[i], 和one[i]

ans = ∑(zero[i] * one[i]),  i∈[0, 31]

def totalHammingDistance(self, nums): """ :type nums: List[int] :rtype: int """ ans = 0 for x in range(32): mask = 1 << x zero = one = 0 for num in nums: if num & mask: one += 1 else: zero += 1 ans += zero * one return ans
X.
https://www.jianshu.com/p/8f127578fe73

那么应该怎么做这道题目呢？题目中的 Explanation 其实是一种误导，我们真的有必要两两组合分别求 Hamming Distance 吗？其实是没有必要的，一次循环能否取得所有的 Hamming Distance？
通过分析得出，Hamming Distance 其实就是每一位的异同。那么这道题目就可以转化为：求x个数每两个数的组合中，每一位的异同数量。想到这里，就会发现其实x个数中每个数的数值并不重要，重要的是每一位有多少个0和多少个1。

https://zhuhan0.blogspot.com/2017/08/leetcode-477-total-hamming-distance.html

A more efficient way to solve this is to iterate through the bits. Since max(nums) < 10^9, I know that the numbers won't take more than 32 bits. Say for one of these bits, there are k numbers with that bit on, so there are n - k numbers with that bit off. Then that particular bit will add k(n - k) to the total hamming distance.

    public int totalHammingDistance(int[] nums) {
        int[] bitCounts = new int[32];
        for (int num : nums) {
            int i = 0;
            while (num > 0) {
                bitCounts[i] += num & 1;
                num >>= 1;
                i++;
            }
        }
        
        int length = nums.length;
        int total = 0;
        for (int count : bitCounts) {
            total += count * (length - count);
        }
        return total;
    }

X. Brute Force
https://github.com/veronikabenkeser/LeetCode/blob/master/477.%20Total%20Hamming%20Distance
http://blog.csdn.net/zhouziyu2011/article/details/53726081

(1)遍历数组nums，对每一个nums[i]，求其余后面的每一个nums[j]的Hamming Distance。

(2)求x与y的Hamming Distance的方法：

---1)先求x^y的结果res。

---2)再依次求32位res的每一位与1进行与操作的结果，若不为0，则Hamming Distance加一。

1.     public int totalHammingDistance(int[] nums) {  
2.         int len = nums.length;  
3.         if (len == 0)  
4.             return 0;  
5.         int result = 0;  
6.         for (int i = 0; i < len - 1; i++) {  
7.             for (int j = i + 1; j < len; j++)  
8.                 result += hammingDistance(nums[i], nums[j]);  
9.         }  
10.         return result;  
11.     }  
12.     public int hammingDistance(int x, int y) {  
13.         int res = x ^ y;  
14.         int count = 0;  
15.         for (int i = 0; i < 32; i++) {  
16.             if ((res & 1) != 0)  
17.                 count++;  
18.             res >>= 1;  
19.         }  
20.         return count;  
21.     }  

https://discuss.leetcode.com/topic/72099/share-my-o-n-c-bitwise-solution-with-thinking-process-and-explanation

LeetCode 169 - Majority Number I

Related: LeetCode 229 + LintCode: Majority Number II
https://leetcode.com/problems/majority-element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

X. Boyer-Moore Voting Algorithm
https://leetcode.com/problems/majority-element/discuss/51828/C%2B%2B-solution-using-Moore's-voting-algorithm-O(n)-runtime-comlexity-an-no-extra-array-or-hash-table
Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element. Below code loops through each element and maintains a count of the element that has the potential of being the majority element. If next element is same then increments the count, otherwise decrements the count. If the count reaches 0 then update the potential index to the current element and sets count to 1.

int majorityElement(vector<int> &num) {
    int majorityIndex = 0;
    for (int count = 1, i = 1; i < num.size(); i++) {
        num[majorityIndex] == num[i] ? count++ : count--;
        if (count == 0) {
            majorityIndex = i;
            count = 1;
        }
    }
        
    return num[majorityIndex];
}

https://discuss.leetcode.com/topic/8692/o-n-time-o-1-space-fastest-solution

You need(may) check if "major" is really a majority element.

    public int majorityElement(int[] num) {

        int major=num[0], count = 1;
        for(int i=1; i<num.length;i++){
            if(count==0){
                count++;
                major=num[i];
            }else if(major==num[i]){
                count++;
            }else count--;
            
        }
        return major;
    }

X. Quick Select

    int majorityElement(vector<int>& nums) {

        nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());

        return nums[nums.size() / 2];

    }

X. 

public int majorityElement1(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length/2];
}

// Hashtable 
public int majorityElement2(int[] nums) {
    Map<Integer, Integer> myMap = new HashMap<Integer, Integer>();
    //Hashtable<Integer, Integer> myMap = new Hashtable<Integer, Integer>();
    int ret=0;
    for (int num: nums) {
        if (!myMap.containsKey(num))
            myMap.put(num, 1);
        else
            myMap.put(num, myMap.get(num)+1);
        if (myMap.get(num)>nums.length/2) {
            ret = num;
            break;
        }
    }
    return ret;
}

// Moore voting algorithm
public int majorityElement3(int[] nums) {
    int count=0, ret = 0;
    for (int num: nums) {
        if (count==0)
            ret = num;
        if (num!=ret)
            count--;
        else
            count++;
    }
    return ret;
}

X. 32n Bit Manipulation
https://leetcode.com/problems/majority-element/discuss/51649/Share-my-solution-Java-Count-bits

We can iterate over the bits of all numbers and for every position find out if ones outnumber the zeros (among all numbers). If this is the case, the corresponding bit of the ret variable (which holds the result) is set. We essentially "construct" the number we look for.

public int majorityElement(int[] num) {

    int ret = 0;

    for (int i = 0; i < 32; i++) {

        int ones = 0, zeros = 0;

        for (int j = 0; j < num.length; j++) {
            if ((num[j] & (1 << i)) != 0) {
                ++ones;
            }
            else
                ++zeros;
        }

        if (ones > zeros)
            ret |= (1 << i);
    }
    
    return ret;
}

The key lies in how to count the number of 1's on a specific bit. Specifically, you need a mask with a 1 on the i-the bit and 0 otherwise to get the i-th bit of each element in nums. The code is as follows.

public int majorityElement(int[] nums) {
    int[] bit = new int[32];
    for (int num: nums)
        for (int i=0; i<32; i++) 
            if ((num>>(31-i) & 1) == 1)
                bit[i]++;
    int ret=0;
    for (int i=0; i<32; i++) {
        bit[i]=bit[i]>nums.length/2?1:0;
        ret += bit[i]*(1<<(31-i));
    }
    return ret;
}

https://discuss.leetcode.com/topic/17446/6-suggested-solutions-in-c-with-explanations

Randomization

Because more than $\lfloor \dfrac{n}{2} \rfloor$ array indices are occupied by the majority element, a random array index is likely to contain the majority element.

This is a really nice idea and works pretty well (16ms running time on the OJ, almost fastest among the C++ solutions). The proof is already given in the suggested solutions.

The code is as follows, randomly pick an element and see if it is the majority one.

    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        srand(unsigned(time(NULL)));
        while (true) {
            int idx = rand() % n;
            int candidate = nums[idx];
            int counts = 0; 
            for (int i = 0; i < n; i++)
                if (nums[i] == candidate)
                    counts++; 
            if (counts > n / 2) return candidate;
        }
    }

X. Divide and Conquer

https://zxi.mytechroad.com/blog/divide-and-conquer/leetcode-169-majority-element/

    int majorityElement(vector<int>& nums) {

        return majorityElement(nums, 0, nums.size() - 1).first;

    }

private:

    pair<int, int> majorityElement(const vector<int>& nums, int l, int r) {

        if (l == r) return {nums[l], 1};

        int mid = l + (r - l) / 2;

        auto ml = majorityElement(nums, l, mid);

        auto mr = majorityElement(nums, mid + 1, r);

        if (ml.first == mr.first) return { ml.first, ml.second + mr.second };

        if (ml.second > mr.second)

            return { ml.first, ml.second + count(nums.begin() + mid + 1, nums.begin() + r + 1, ml.first) };

        else

            return { mr.first, mr.second + count(nums.begin() + l, nums.begin() + mid + 1, mr.first) };

    }

    int majorityElement(vector<int>& nums) {

        return majorityElement(nums, 0, nums.size() - 1);

    }

private:

    int majorityElement(const vector<int>& nums, int l, int r) {

        if (l == r) return nums[l];

        const int m = l + (r - l) / 2;

        const int ml = majorityElement(nums, l, m);

        const int mr = majorityElement(nums, m + 1, r);

        if (ml == mr) return ml;

        return count(nums.begin() + l, nums.begin() + r + 1, ml) >

               count(nums.begin() + l, nums.begin() + r + 1, mr)

               ? ml : mr;

    }

https://leetcode.com/articles/majority-element/

If we know the majority element in the left and right halves of an array, we can determine which is the global majority element in linear time.

Here, we apply a classical divide & conquer approach that recurses on the left and right halves of an array until an answer can be trivially achieved for a length-1 array. Note that because actually passing copies of subarrays costs time and space, we instead pass lo and hi indices that describe the relevant slice of the overall array. In this case, the majority element for a length-1 slice is trivially its only element, so the recursion stops there. If the current slice is longer than length-1, we must combine the answers for the slice's left and right halves. If they agree on the majority element, then the majority element for the overall slice is obviously the same1. If they disagree, only one of them can be "right", so we need to count the occurrences of the left and right majority elements to determine which subslice's answer is globally correct. The overall answer for the array is thus the majority element between indices 0 and $n$

• Time complexity : $O(nlgn)$
  Each recursive call to majority_element_rec performs two recursive calls on subslices of size $\frac{n}{2}$ and two linear scans of length $n$. Therefore, the time complexity of the divide & conquer approach can be represented by the following recurrence relation:
  $T(n) = 2T(\frac{n}{2}) + 2n$
  
  
  By the master theorem, the recurrence satisfies case 2, so the complexity can be analyzed as such:
  $\begin{aligned} T(n) &amp;= \Theta(n^{log_{b}a}\log n) \\ &amp;= \Theta(n^{log_{2}2}\log n) \\ &amp;= \Theta(n \log n) \\ \end{aligned}$

  private int countInRange(int[] nums, int num, int lo, int hi) {

    int count = 0;

    for (int i = lo; i <= hi; i++) {

      if (nums[i] == num) {

        count++;

      }

    }

    return count;

  }

  private int majorityElementRec(int[] nums, int lo, int hi) {

    // base case; the only element in an array of size 1 is the majority

    // element.

    if (lo == hi) {

      return nums[lo];

    }

    // recurse on left and right halves of this slice.

    int mid = (hi - lo) / 2 + lo;

    int left = majorityElementRec(nums, lo, mid);

    int right = majorityElementRec(nums, mid + 1, hi);

    // if the two halves agree on the majority element, return it.

    if (left == right) {

      return left;

    }

    // otherwise, count each element and return the "winner".

    int leftCount = countInRange(nums, left, lo, hi);

    int rightCount = countInRange(nums, right, lo, hi);

    return leftCount > rightCount ? left : right;

  }

  public int majorityElement(int[] nums) {

    return majorityElementRec(nums, 0, nums.length - 1);

  }

This idea is very algorithmic. However, the implementation of it requires some careful thought about the base cases of the recursion. The base case is that when the array has only one element, then it is the majority one.

    int majorityElement(vector<int>& nums) {
        return majority(nums, 0, nums.size() - 1);
    }
private:
    int majority(vector<int>& nums, int left, int right) {
        if (left == right) return nums[left];
        int mid = left + ((right - left) >> 1);
        int lm = majority(nums, left, mid);
        int rm = majority(nums, mid + 1, right);
        if (lm == rm) return lm;
        return count(nums.begin() + left, nums.begin() + right + 1, lm) > count(nums.begin() + left, nums.begin() + right + 1, rm) ? lm : rm;
    }

X. Bit counting
https://discuss.leetcode.com/topic/6286/share-my-solution-java-count-bits
We can iterate over the bits of all numbers and for every position find out if ones outnumber the zeros (among all numbers). If this is the case, the corresponding bit of the ret variable (which holds the result) is set. We essentially "construct" the number we look for.

public int majorityElement(int[] num) {

    int ret = 0;

    for (int i = 0; i < 32; i++) {

        int ones = 0, zeros = 0;

        for (int j = 0; j < num.length; j++) {
            if ((num[j] & (1 << i)) != 0) {
                ++ones;
            }
            else
                ++zeros;
        }

        if (ones > zeros)
            ret |= (1 << i);
    }
    
    return ret;
}

    int majorityElement(vector<int>& nums) {
        int major = 0, n = nums.size();
        for (int i = 0, mask = 1; i < 32; i++, mask <<= 1) {
            int bitCounts = 0;
            for (int j = 0; j < n; j++) {
                if (nums[j] & mask) bitCounts++;
                if (bitCounts > n / 2) {
                    major |= mask;
                    break;
                }
            }
        } 
        return major;
    } 

    public int majorityElement(int[] nums) {
        int majorityCount = nums.length/2;

        for (int num : nums) {
            int count = 0;
            for (int elem : nums) {
                if (elem == num) {
                    count += 1;
                }
            }

            if (count > majorityCount) {
                return num;
            }

        }

        return -1; 
    }