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.
f(1,3) = 01, 11 -> 1
f(3,5) = 11, 101 ->2
f(5,1) = 101, 001 ->1
Sum = 1 + 2 + 1 = 4.
- Count frequency of odd and even numbers in array
- ANS += even_frequency * odd_frequency
- Divide each number by 2
- Repeat for 32 times(assuming numbers are 32 bit)
Time Complexity : O(n.log-n)
def countBitsSum(arr): return sum([bin(a^b).count("1") for a,b in itertools.combinations(arr,2)])
It's actually similar to finding total hamming distance.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.