Sum of Count of Different bits


  • 0
    Y

    A function f(a,b) equals number of bits two numbers a and b differ in the base 2 representation. Given a set of numbers in an array A [1, 3, 5], find the sum of f(i,j) over all pairs of numbers.

    Example: [1,3,5]
    f(1,3) = 01, 11 -> 1
    f(3,5) = 11, 101 ->2
    f(5,1) = 101, 001 ->1
    Sum = 1 + 2 + 1 = 4.


  • 2
    S
    1. Count frequency of odd and even numbers in array
    2. ANS += even_frequency * odd_frequency
    3. Divide each number by 2
    4. Repeat for 32 times(assuming numbers are 32 bit)

    Time Complexity : O(n.log-n)


  • 0
    S
    def countBitsSum(arr):
        return sum([bin(a^b).count("1") for a,b in itertools.combinations(arr,2)])

  • 0
    K

    It's actually similar to finding total hamming distance.
    https://leetcode.com/problems/total-hamming-distance/#/description


Log in to reply
 

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