Sum of special numbers

Easy
0/40
Average time to solve is 19m
profile
Contributed by
2 upvotes

Problem statement

You are given an array of N numbers. Your task is to return the sum of all special numbers present in it.

A number is said to be special if the count of 0’s is equal to the count of 1's in its binary representation.

Note : We only consider 0’s to the right of Most Significant Bit while calculating the count of 0’s in a number’s binary representation, ie: 25=(000011001)2 has 3 bits equal to 1 and 2 bits equal to 0.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases to run. Then the test cases follow.

The first line contains a single integer N, where N represents the size of the array.

The next line contains N integers, denoting the elements of the given array.
Output Format : 
For each test case print a single integer denoting the sum of special numbers in the array.

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.
Constraints : 
1 <= T <= 10      
1 <= N <= 2 * 10^4
1 <= a[i] <= 10^9
Time limit: 1 sec
Sample Input 1 : 
2
6
1 2 3 4 5 6
4
4 8 16 32
Sample Output 1 : 
2
0
Explanation of sample input 1 : 
For test case 1:
The binary representation of 2 is (10)2 it has an equal number of bits with values 1 and value 0.
Rest all the numbers have unequal count of bits with values 0 and 1.
Hence the final sum is 0+2+0+0+0+0 = 2

For test case 2:
None of the array elements has an equal count of bits with values 0 and 1.
4=(100) , 8=(1000) , 16=(10000) ,32=(100000)
Sample Input 2 : 
2
2
12 9 
1
12
Sample Output 2 : 
 21
 12
Hint

How to count the number of set bits in a number? Can you directly count the number of set bits in the binary representation of a number?

Approaches (1)
Bit Manipulation

For each number of the array, we directly calculate the count of bits with value = 1 in its binary representation using __builtin_popcount.

 

To calculate the count of bits with value = 0, we need to find the position of the leftmost bit with value 1 and deduct the count of 1’s from its position.

For example: 49 = (0000000110001)2 

                      __builtin_popcount(49) = 3,

                      Position of MSB = log2(49) = 5, as indexing is 0 based, so there are total 6 bits

                      Therefore count of 0’s = 6-3 = 3

 

The steps are as follows:

  1. For each element , count of 1’s = __builtin_popcount.(ai)
  2. For each element , count of 0’s = log2(ai) +1 - __builtin_popcount.(ai)
  3. If count of 0’s is equal to count of 1’s, simply add ai to final answer

 

Time Complexity

O( N*log(X) ), where ‘N’ is the length of the array given, and X is the maximum valuer of ai in the array.

 

For each test case, we iterate through an array to evaluate its every element, __builtin_popcount( ai ) has a time complexity of O(number of bits in ai ).

 

Space Complexity

O(1)

 

No auxiliary space used.

Code Solution
(100% EXP penalty)
Sum of special numbers
Full screen
Console