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 of elements is:
- 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, the 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 bits on a map, then find the sum of elements having a unique count of set bits. 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 bits.
- 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:
C++
// C++ program for the approach#include <iostream>#include <bits/stdc++.h> using namespace std;// Function to count the number// of set bits in an integer Nint setBitCount(int n){ // Stores the count of set bits int ans = 0; // Iterate until N is non-zero while (n) { ans += n & 1; n >>= 1; } // Stores the resultant count return ans;}// Function to calculate sum of all array// elements whose count of set bits are uniqueint getSum(int *arr, int n){ // Stores frequency of all possible // count of set bits map<int, int> mp; // Stores the sum of array elements int ans = 0; // Traverse the array for(int i = 0; i < n; i++) { // Count the number of set bits int key = setBitCount(arr[i]); mp[key] += 1; } // Traverse the array // And Update the value of ans for(int i = 0; i < n; i++) { int key = setBitCount(arr[i]); // If frequency is 1 if (mp[key] == 1) ans += arr[i]; } cout << ans;}// Driver Codeint main(){ int arr[5] = {8, 3, 7, 5, 3}; int n = sizeof(arr) / sizeof(arr[0]); getSum(arr, n); return 0;}// This code is contributed by rohitsingh07052 |
Java
// Java program for the approachimport java.util.*;class GFG{ // Function to count the number // of set bits in an integer N static int setBitCount(int n) { // Stores the count of set bits int ans = 0; // Iterate until N is non-zero while (n != 0) { ans += n & 1; n >>= 1; } // Stores the resultant count return ans; } // Function to calculate sum of all array // elements whose count of set bits are unique static void getSum(int []arr, int n) { // Stores frequency of all possible // count of set bits Map<Integer,Integer> mp = new HashMap<Integer,Integer>(); // Stores the sum of array elements int ans = 0; // Traverse the array for(int i = 0; i < n; i++) { // Count the number of set bits int key = setBitCount(arr[i]); if(mp.containsKey(key)) mp.put(key,mp.get(key) + 1); else mp.put(key, 1); } // Traverse the array // And Update the value of ans for(int i = 0; i < n; i++) { int key = setBitCount(arr[i]); // If frequency is 1 if (mp.containsKey(key) && mp.get(key) == 1) ans += arr[i]; } System.out.print(ans); } // Driver Code public static void main(String args[]) { int []arr = {8, 3, 7, 5, 3}; int n = arr.length; getSum(arr, n); }}// This code is contributed by SURENDRA_GANGWAR. |
Python3
# Python3 program for the approach# Function to count the number# of set bits in an integer Ndef setBitCount(n): # Stores the count of set bits ans = 0 # Iterate until N is non-zero while n: ans += n & 1 n >>= 1 # Stores the resultant count return ans# Function to calculate sum of all array# elements whose count of set bits are uniquedef getSum(arr): # Stores frequency of all possible # count of set bits mp = {} # Stores the sum of array elements ans = 0 # Traverse the array for i in arr: # Count the number of set bits key = setBitCount(i) mp[key] = [0, i] # Traverse the array for i in arr: key = setBitCount(i) mp[key][0] += 1 # Update the value of ans for i in mp: # If frequency is 1 if mp[i][0] == 1: ans += mp[i][1] print(ans)# Driver Codearr = [8, 3, 7, 5, 3]getSum(arr) |
C#
// C# program for the approachusing System;using System.Collections.Generic;class solution{ // Function to count the number// of set bits in an integer Nstatic int setBitCount(int n){ // Stores the count of set bits int ans = 0; // Iterate until N is non-zero while (n>0) { ans += n & 1; n >>= 1; } // Stores the resultant count return ans;}// Function to calculate sum of all array// elements whose count of set bits are uniquestatic void getSum(int []arr, int n){ // Stores frequency of all possible // count of set bits Dictionary<int, int> mp = new Dictionary<int,int>(); // Stores the sum of array elements int ans = 0; // Traverse the array for(int i = 0; i < n; i++) { // Count the number of set bits int key = setBitCount(arr[i]); if(mp.ContainsKey(key)) mp[key] += 1; else mp[key] = 1; } // Traverse the array // And Update the value of ans for(int i = 0; i < n; i++) { int key = setBitCount(arr[i]); // If frequency is 1 if (mp[key] == 1) ans += arr[i]; } Console.Write(ans);}// Driver Codepublic static void Main(){ int []arr = {8, 3, 7, 5, 3}; int n = arr.Length; getSum(arr, n);}}// This code is contributed by ipg2016107. |
Javascript
<script>// JavaScript program for the above approach// Function to count the number // of set bits in an integer N function setBitCount(n) { // Stores the count of set bits let ans = 0; // Iterate until N is non-zero while (n != 0) { ans += n & 1; n >>= 1; } // Stores the resultant count return ans; } // Function to calculate sum of all array // elements whose count of set bits are unique function getSum(arr, n) { // Stores frequency of all possible // count of set bits let mp = new Map(); // Stores the sum of array elements let ans = 0; // Traverse the array for(let i = 0; i < n; i++) { // Count the number of set bits let key = setBitCount(arr[i]); if(mp.has(key)) mp.set(key,mp.get(key) + 1); else mp.set(key, 1); } // Traverse the array // And Update the value of ans for(let i = 0; i < n; i++) { let key = setBitCount(arr[i]); // If frequency is 1 if (mp.has(key) && mp.get(key) == 1) ans += arr[i]; } document.write(ans); }// Driver Code let arr = [8, 3, 7, 5, 3]; let n = arr.length; getSum(arr, n); </script> |
Output:
15
Time Complexity: O(N)
Space Complexity: O(N) as we are using a map to store the count of the distinct bits.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
