
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:
- arr[0] = 8 = (1000)2, has 1 set bits.
- arr[1] = 3 = (11)2, has 2 set bits.
- arr[2] = 7 = (111)2, has 3 set bits.
- arr[3] = 5 = (101)2, has 2 set bits.
- arr[4] = 3 = (11)2, 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
|
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.
0 comments:
Post a Comment