Suma de elementos de array cuyo recuento de bits establecidos es único

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: 

  1. arr[0] = 8 = (1000) 2 , tiene 1 conjunto de bits.
  2. arr[1] = 3 = (11) 2 , tiene 2 bits establecidos.
  3. arr[2] = 7 = (111) 2 , tiene 3 bits establecidos.
  4. arr[3] = 5 = (101) 2 , tiene 2 bits establecidos.
  5. 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:

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>        
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *