Sum of array elements whose count of set bits are unique

Sum of array elements whose count of set bits are unique

Given an array arr[] consisting of N positive integers, the task is to find the sum of all array elements having a distinct count of set bits in the array.

Examples:

Input: arr[] = {8, 3, 7, 5, 3}
Output: 15
Explanation:
The count of set bits in each array elements are:

1. arr[0] = 8 = (1000)₂, has 1 set bits.
2. arr[1] = 3 = (11)₂, has 2 set bits.
3. arr[2] = 7 = (111)₂, has 3 set bits.
4. arr[3] = 5 = (101)₂, has 2 set bits.
5. arr[4] = 3 = (11)₂, has 2 set bits.

Therefore, the number of array elements whose count of set bits are unique are 8 and 7. Therefore, required sum = 8 + 7 = 15.

Input: arr[] = {4, 5, 3, 5, 3, 2}
Output: 0

Approach: The idea is to store the element with the corresponding count of set bit in a map then find the sum of elements having a unique count of set bit. Follow the steps below to solve the problem:

• Initialize a variable, say sum to store the resultant sum of elements, and a Map, say M that stores the elements having a particular count of set bit.
• Traverse the array arr[] and store the element arr[i] according to the set bit count in a Map M.
• Now, traverse the map and if the frequency of any set bit count is 1 then add the corresponding value associated with it in the variable sum.
• After completing the above steps, print the value of the sum as the result. 

Below is the implementation of the above approach:

Python3

def setBitCount(n):               ans = 0                 while n:            ans += n & 1         n >>= 1                     return ans       def getSum(arr):                    mp = {}                 ans = 0                 for i in arr:                           key = setBitCount(i)         mp[key] = [0, i]             for i in arr:         key = setBitCount(i)         mp[key][0] += 1                 for i in mp:                           if mp[i][0] == 1:             ans += mp[i][1]        print(ans)       arr = [8, 3, 7, 5, 3] getSum(arr)

Output:

15

Time Complexity: O(N)
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)