InterviewBit Academy is now Scaler!
Learn Tech Skills from Scratch @ Scaler EDGE

Sum of pairwise Hamming Distance


Problem Setter: yashpal1995 Problem Tester: amitkgupta94

Problem Description

Hamming distance between two non-negative integers is defined as the number of positions at which the corresponding bits are different.

Given an array A of N non-negative integers, find the sum of hamming distances of all pairs of integers in the array. Return the answer modulo 1000000007.



Problem Constraints

1 <= |A| <= 200000

1 <= A[i] <= 109



Input Format

First and only argument is array A.



Output Format

Return one integer, the answer to the problem.



Example Input

Input 1:

 A = [1]

Input 2:

 A = [2, 4, 6]



Example Output

Output 1:

 0

Output 2:

 8



Example Explanation

Explanation 1:

 No pairs are formed.

Explanation 2:

 We return, f(2, 2) + f(2, 4) + f(2, 6) + f(4, 2) + f(4, 4) + f(4, 6) + f(6, 2) + f(6, 4) + f(6, 6) = 8



NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Sum of pairwise Hamming Distance on Interview Code Editor
Sign Up
to access hints and editorial solutions for Sum of pairwise Hamming Distance
Asked In:

Discussion


Loading...
Click here to start solving coding interview questions