5-line O(N) time O(1) space, simply a math problem: sum ones*(N-ones) with detailed explanation


  • 0

    Key observation: Total Hamming distance can be decomposed into contributions from each bit position, and we calculate each of them independently.

    Consider each 32-bit integer xm=1:N as a 32D 0-1 vector: e.g.,
    x1: [1, 1, 0, 0, 1, ..., 0, 1]
    x2: [0, 1, 0, 0, 1, ..., 0, 0]
    x3: [0, 0, 1, 0, 0, ..., 0, 1]
    ...
    xN: [1, 0, 0, 0, 1, ..., 1, 1].

    For each "column" i (i.e., i-position bit), we count the number of 1 bits onesi, then the contribution Hamming distance from i-position bit is simply

    • onesi*(N - onesi).

    Sum up all position i and we have the answer Σi=1:32onesi*(N - onesi). The times complexity is O(8N sizeof(int)).

        int totalHammingDistance(vector<int>& nums) {
          int res = 0;
          for (int i = 1, ones = 0; (ones = 0), i; i<<=1) {
            for (int n:nums) if (n&i) ++ones;
            res += ones*(nums.size()-ones);
          }
          return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.