Dada una array de enteros que contienen elementos duplicados. La tarea es encontrar la suma de todos los elementos impares en la array dada. Esa es la suma de todos esos elementos cuya frecuencia es impar en la array.
Ejemplos:
Input : arr[] = {1, 1, 2, 2, 3, 3, 3}
Output : 9
The odd occurring element is 3, and it's number
of occurrence is 3. Therefore sum of all 3's in the
array = 9.
Input : arr[] = {10, 20, 30, 40, 40}
Output : 60
Elements with odd frequency are 10, 20 and 30.
Sum = 60.
Enfoque :
- Recorra la array y use un mapa en C++ para almacenar la frecuencia de los elementos de la array de modo que la clave del mapa sea el elemento de la array y el valor sea su frecuencia en la array.
- Luego, recorra el mapa para encontrar la frecuencia de los elementos y verifique si es impar, si es impar, luego agregue este elemento a la suma.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find the sum of all odd
// occurring elements in an array
#include <bits/stdc++.h>
using namespace std;
// Function to find the sum of all odd
// occurring elements in an array
int findSum(int arr[], int N)
{
// Store frequencies of elements
// of the array
unordered_map<int, int> mp;
for (int i = 0; i < N; i++)
mp[arr[i]]++;
// variable to store sum of all
// odd occurring elements
int sum = 0;
// loop to iterate through map
for (auto itr = mp.begin(); itr != mp.end(); itr++) {
// check if frequency is odd
if (itr->second % 2 != 0)
sum += (itr->first) * (itr->second);
}
return sum;
}
// Driver Code
int main()
{
int arr[] = { 10, 20, 20, 10, 40, 40, 10 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findSum(arr, N);
return 0;
}
Java
// Java program to find the sum of all odd
// occurring elements in an array
import java.util.*;
class GFG
{
// Function to find the sum of all odd
// occurring elements in an array
static int findSum(int arr[], int N)
{
// Store frequencies of elements
// of the array
Map<Integer,Integer> mp = new HashMap<>();
for (int i = 0; i < N; i++)
mp.put(arr[i],mp.get(arr[i])==null?1:mp.get(arr[i])+1);
// variable to store sum of all
// odd occurring elements
int sum = 0;
// loop to iterate through map
for (Map.Entry<Integer,Integer> entry : mp.entrySet())
{
// check if frequency is odd
if (entry.getValue() % 2 != 0)
sum += (entry.getKey()) * (entry.getValue());
}
return sum;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 10, 20, 20, 10, 40, 40, 10 };
int N = arr.length;
System.out.println(findSum(arr, N));
}
}
/* This code is contributed by PrinciRaj1992 */
Python3
# Function to find sum of all odd # occurring elements in an array import collections def findsum(arr, N): # Store frequencies of elements # of an array in dictionary mp = collections.defaultdict(int) for i in range(N): mp[arr[i]] += 1 # Variable to store sum of all # odd occurring elements sum = 0 # loop to iterate through dictionary for i in mp: # Check if frequency is odd if (mp[i] % 2 != 0): sum += (i * mp[i]) return sum # Driver Code arr = [ 10, 20, 20, 10, 40, 40, 10 ] N = len(arr) print (findsum(arr, N)) # This code is contributed # by HardeepSingh.
C#
// C# program to find the sum of all odd
// occurring elements in an array
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the sum of all odd
// occurring elements in an array
public static int findSum(int[] arr, int N)
{
// Store frequencies of elements
// of the array
Dictionary<int,
int> mp = new Dictionary<int,
int>();
for (int i = 0; i < N; i++)
{
if (mp.ContainsKey(arr[i]))
mp[arr[i]]++;
else
mp.Add(arr[i], 1);
}
// variable to store sum of all
// odd occurring elements
int sum = 0;
// loop to iterate through map
foreach (KeyValuePair<int,
int> entry in mp)
{
// check if frequency is odd
if (entry.Value % 2 != 0)
sum += entry.Key * entry.Value;
}
return sum;
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 10, 20, 20, 10, 40, 40, 10 };
int n = arr.Length;
Console.WriteLine(findSum(arr, n));
}
}
// This code is contributed by
// sanjeev2552
Javascript
<script>
// Javascript program to find the sum of all odd
// occurring elements in an array
// Function to find the sum of all odd
// occurring elements in an array
function findSum(arr, N)
{
// Store frequencies of elements
// of the array
let mp = new Map();
for (let i = 0; i < N; i++) {
if (mp.has(arr[i])) {
mp.set(arr[i], mp.get(arr[i]) + 1)
} else {
mp.set(arr[i], 1)
}
}
// variable to store sum of all
// odd occurring elements
let sum = 0;
// loop to iterate through map
for (let itr of mp) {
// check if frequency is odd
if (itr[1] % 2 != 0)
sum += (itr[0]) * (itr[1]);
}
return sum;
}
// Driver Code
let arr = [10, 20, 20, 10, 40, 40, 10];
let N = arr.length
document.write(findSum(arr, N));
// This code is contributed by gfgking.
</script>
Producción:
30
Complejidad de tiempo : O(N), donde N es el número de elementos en la array.
Espacio Auxiliar: O(N)
Método 2: Uso de las funciones integradas de python:
- Cuente las frecuencias de cada elemento usando la función Contador
- Recorra el diccionario de frecuencias y sume todos los elementos con frecuencia impar de ocurrencia multiplicada por su frecuencia.
A continuación se muestra la implementación:
Python3
# Python3 implementation of the above approach from collections import Counter def sumOdd(arr, n): # Counting frequency of every # element using Counter freq = Counter(arr) # Initializing sum 0 sum = 0 # Traverse the frequency and print all # sum all elements with odd frequency # multiplied by its frequency for it in freq: if freq[it] % 2 != 0: sum = sum + it*freq[it] print(sum) # Driver code arr = [10, 20, 30, 40, 40] n = len(arr) sumOdd(arr, n) # This code is contributed by vikkycirus
Producción:
60
Complejidad temporal: O(N), donde N es el número de elementos de la array.
Espacio Auxiliar: O(N)