Java O(n) runtime solution. 44ms


  • 0
    M
    public class Solution {
        public int totalHammingDistance(int[] nums) {
            if(nums == null || nums.length == 0) return 0;
            int count = 0, mask = 1;
            for(int i = 0; i < 32; ++i){
                int numOfZeros = 0;
                for(int x : nums){
                    if ((x & mask)==0) numOfZeros++;
                }
                count += (numOfZeros)*(nums.length - numOfZeros);
                mask <<= 1;
            }
            return count;
        }
    }
    

    Runtime analysis:

    • If we consider the integer to be of 4-bytes, as I have considered here, each element in the input array is touched 32 times. Therefore, the complexity is O(32N) which is equivalent to O(N), ignoring constants.

    • To be more general, the run time is O(NlogM) where M is the maximum value of the integer.


Log in to reply
 

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