Simple example for the "Java O(n) time O(1) Space" Solution


  • 4
    B

    The idea is same as https://discuss.leetcode.com/topic/72092/java-o-n-time-o-1-space
    Assuming we have an array of five integers a, b, c, d, e as follow.
    We examine the digits one by one from the last digit.
    Count the number of integers whose last digit is 1, assign the value to ones

        a = 0 0 0 1 0
        b = 1 0 0 1 1
        c = 0 1 0 0 1
        d = 1 0 0 1 0
        e = 0 0 0 1 0
                    ↑
        ones: b, c
        zeros: a, d, e
        
        pairs that make distance are:
        b: a, d, e
        c: a, d, e
    
        So we have 2 ones and 5 - 2 = 3 zeros
        Total distance = 2 * 3
        then we move the pointer one position left, i.e. all the numbers right shift by 1 (num >>> 1)
    

    The code is as follows.

    public int totalHammingDistance(int[] nums) {
            int res = 0, len = nums.length;
            for(int i = 0; i < 32; i++) { //32 digits in integers
                int ones = 0; 
                for(int j = 0; j < len; j++) {
                    if((nums[j] & 1) == 1) ones++;
                    nums[j] = nums[j] >>> 1;
                }
                res = res + ones * (len - ones);
            }
            return res;
    }
    

Log in to reply
 

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