Friday, February 26, 2021

Published February 26, 2021 by Anonymous with 0 comment

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)2, has 1 set bits.
  2. arr[1] = 3 = (11)2, has 2 set bits.
  3. arr[2] = 7 = (111)2, has 3 set bits.
  4. arr[3] = 5 = (101)2, has 2 set bits.
  5. 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

  

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?)

      edit

0 comments:

Post a Comment