Pattern Sum

Easy

0/40

Average time to solve is 15m

Contributed by

5 upvotes

Problem statement

Given an array/list ‘Arr’, and two integers ‘A’ and ‘B’ which represent the number of 0’s and 1’s in the binary form, find the sum of all the numbers in the array ‘Arr’ having the same number of 0’s and 1’s in their binary representation.

The answer can be large so return answer modulo 1000000007

For Example

Let Arr[] = {2, 4, 10} , A = 1 and B = 1

In this example, the binary representation of the array {2, 4, 10} is {10, 100, 1010} and according to the problem statement, only 2 fulfills the given condition, i.e., have one 0-bit count and one 1-bit count. Hence, the sum of all the numbers is 2.

Note :

Do not count zeros to the left of the most significant set bit.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains an integer ‘N’ denoting the array’s length.

The second line of the test case contains two integers, ‘A’ and ‘B’, denoting the number of ‘0’ bits and ‘1’ bits, respectively.

The third line of the test case contains an array ‘Arr’ of ‘N’ integers.

Output format :

For each test case, print an integer denoting the sum of all numbers matching the given pattern.    

Output for each test case will be printed in a separate line.

Note:

 You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints:

1 <= T <= 10
1 <= N <= 10^5
0 <= Arr[i] <= 10^9
0 <= A <= 31
0 <= B <= 31
0 <= A + B <= 31

Time Limit: 1sec

Sample Input 1:

Sample Output 1:

2
21

Explanation For Sample Output 1:

In the first test case, the binary representation of the array {2, 4, 10} is {10, 100, 1010} and according to the problem statement, only 2 fulfills the given condition, i.e., have one 0-bit count and one 1-bit count, so the sum of all the numbers is 2.

In the second test case, only 9 and 12, i.e., 1001 and 1100, have two 0-bit counts and two 1-bit counts in their binary representation, so the sum of all the numbers is 21.

Sample Input 2:

Sample Output 2:

7
4

Hint 1

Count the total number of 0’s and 1’s bit in every number of the array.

Approaches (1)

Approach 1

Bit Manipulation

The approach is simple; we have to calculate the total number of zeros and ones in the bitwise representation of all the given elements in our array.

The steps are as follows:

Create a variable ‘Ans’ = 0.
Iterate over the entire array ‘Arr’ from 1 to N(say iterator be i):
1. Calculate the total number of 0s and 1s in the binary representation of ‘Arr[i]’.
2. If the number of 0s and 1s is equal to the ‘A’ and ‘B’ respectively, update ‘Ans’ = (‘Ans’ + ‘Arr[i]’) % ‘MOD’.
Return ‘Ans’.

Time Complexity

O(N * log(N)), where ‘N’ is the length of the given array.

Since we are iterating through the whole array and then dividing each element by 2 until ‘Arr[i]’ != 0, which is a log(N) process, so the total complexity is O(N * log(N)).

Space Complexity

O(1).

We don't have to create extra space, so the space complexity is O(1).

(100% EXP penalty)

Pattern Sum

Console