We define f (X, Y) as number of different corresponding bits in binary representation of X and Y. For example, f (2, 7) = 2, since binary representation of 2 and 7 are 010 and 111, respectively. The first and the third bit differ, so f (2, 7) = 2.
You are given an array A of N integers, A_{1}, A_{2} ,…, A_{N}. Find sum of f(A_{i}, A_{j}) for all ordered pairs (i, j) such that 1 ≤ i, j ≤ N. Return the answer modulo 10^{9}+7.
Example 1:
Input: N = 2
A = {2, 4}
Output: 4
Explaintion: We return
f(2, 2) + f(2, 4) +
f(4, 2) + f(4, 4) =
0 + 2 +
2 + 0 = 4.
Example 2:
Input: N = 3
A = {1, 3, 5}
Output: 8
Explaination: We return
f(1, 1) + f(1, 3) + f(1, 5) +
f(3, 1) + f(3, 3) + f(3, 5) +
f(5, 1) + f(5, 3) + f(5, 5) =
0 + 1 + 1 +
1 + 0 + 2 +
1 + 2 + 0 = 8.
Your Task:
You do not need to read input or print anything. Your task is to complete the function countBits() which takes the value N and the array A as input parameters and returns the desired count modulo 10^{9}+7.
Expected Time Complexity: O(N * log_{2}(Max(A_{i})))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
2^{0} ≤ A[i] < 2^{31}

见题面

见题面