Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar la suma de todos los elementos de la array que tienen un recuento distinto de bits establecidos en la array.
Ejemplos:
Entrada: arr[] = {8, 3, 7, 5, 3}
Salida: 15
Explicación:
El recuento de bits establecidos en cada array de elementos es:
- arr[0] = 8 = (1000) 2 , tiene 1 conjunto de bits.
- arr[1] = 3 = (11) 2 , tiene 2 bits establecidos.
- arr[2] = 7 = (111) 2 , tiene 3 bits establecidos.
- arr[3] = 5 = (101) 2 , tiene 2 bits establecidos.
- arr[4] = 3 = (11) 2 , tiene 2 bits establecidos.
Por lo tanto, el número de elementos de la array cuyo recuento de bits establecidos es único es 8 y 7. Por lo tanto, la suma requerida = 8 + 7 = 15.
Entrada: arr[] = {4, 5, 3, 5, 3, 2}
Salida: 0
Enfoque: la idea es almacenar el elemento con el recuento correspondiente de bits establecidos en un mapa , luego encontrar la suma de los elementos que tienen un recuento único de bits establecidos. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos sum para almacenar la suma resultante de elementos, y un Map , digamos M que almacene los elementos que tienen un número particular de bits establecidos.
- Recorra la array arr[] y almacene el elemento arr[i] de acuerdo con el recuento de bits establecido en un Map M .
- Ahora, recorra el mapa y si la frecuencia de cualquier conteo de bits establecido es 1, agregue el valor correspondiente asociado con él en la variable sum .
- Después de completar los pasos anteriores, imprima el valor de la suma como resultado.
A continuación se muestra la implementación del enfoque anterior:
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 N int 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 unique int 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 Code int 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 approach import 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 N def 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 unique def 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 Code arr = [8, 3, 7, 5, 3] getSum(arr)
C#
// C# program for the approach using System; using System.Collections.Generic; class solution{ // 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 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 Code public 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>
15
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA