Dada una array de enteros que contienen elementos duplicados. La tarea es encontrar la suma de todos los elementos que aparecen menos en la array dada. Esa es la suma de todos esos elementos cuya frecuencia es mínima en la array.
Ejemplos :
Input : arr[] = {1, 1, 2, 2, 3, 3, 3, 3}
Output : 2
The least occurring element is 1 and 2 and it's number
of occurrence is 2. Therefore sum of all 1's and 2's in the
array = 1+1+2+2 = 6.
Input : arr[] = {10, 20, 30, 40, 40}
Output : 60
Elements with least frequency are 10, 20, 30.
Their sum = 10 + 20 + 30 = 60.
Enfoque :
- Recorra la array y use un mapa_desordenado 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 del elemento mínimo que ocurre.
- Ahora, para encontrar la suma, recorra el mapa nuevamente y para todos los elementos con una frecuencia mínima, busque la frecuencia_del_elemento_mínimo_que ocurre*elemento_mínimo_que ocurre y encuentre su suma.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the sum of all minimum
// occurring elements in an array
#include <bits/stdc++.h>
using namespace std;
// Function to find the sum of all minimum
// 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]]++;
// Find the min frequency
int minFreq = INT_MAX;
for (auto itr = mp.begin(); itr != mp.end(); itr++) {
if (itr->second < minFreq) {
minFreq = itr->second;
}
}
// Traverse the map again and find the sum
int sum = 0;
for (auto itr = mp.begin(); itr != mp.end(); itr++) {
if (itr->second == minFreq) {
sum += itr->first * itr->second;
}
}
return sum;
}
// Driver Code
int main()
{
int arr[] = { 10, 20, 30, 40, 40 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findSum(arr, N);
return 0;
}
Java
// Java program to find the sum of all minimum
// occurring elements in an array
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
class GFG
{
// Function to find the sum of all minimum
// 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);
// Find the min frequency
int minFreq = Integer.MAX_VALUE;
minFreq = Collections.min(mp.entrySet(),
Comparator.comparingInt(Map.Entry::getKey)).getValue();
// Traverse the map again and find the sum
int sum = 0;
for (Map.Entry<Integer,Integer> entry : mp.entrySet())
{
if (entry.getValue() == minFreq)
{
sum += entry.getKey() * entry.getValue();
}
}
return sum;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 10, 20, 30, 40, 40 };
int N = arr.length;
System.out.println( findSum(arr, N));
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 program to find theSum of all # minimum occurring elements in an array import math as mt # Function to find theSum of all minimum # occurring elements in an array def findSum(arr, N): # Store frequencies of elements # of the array mp = dict() for i in arr: if i in mp.keys(): mp[i] += 1 else: mp[i] = 1 # Find the min frequency minFreq = 10**9 for itr in mp: if mp[itr]< minFreq: minFreq = mp[itr] # Traverse the map again and # find theSum Sum = 0 for itr in mp: if mp[itr]== minFreq: Sum += itr * mp[itr] return Sum # Driver Code arr = [ 10, 20, 30, 40, 40] N = len(arr) print(findSum(arr, N)) # This code is contributed by # mohit kumar 29
C#
// C# program to find the sum of all minimum
// occurring elements in an array
using System;
using System.Collections.Generic;
class GFG{
// Function to find the sum of all minimum
// occurring elements in an array
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);
}
}
// Find the min frequency
int minFreq = Int32.MaxValue;
foreach(KeyValuePair<int, int> itr in mp)
{
if (itr.Value < minFreq)
{
minFreq = itr.Value;
}
}
// Traverse the map again and find the sum
int sum = 0;
foreach(KeyValuePair<int, int> itr in mp)
{
if (itr.Value == minFreq)
{
sum += itr.Key * itr.Value;
}
}
return sum;
}
// Driver code
static void Main()
{
int[] arr = { 10, 20, 30, 40, 40 };
int N = arr.Length;
Console.Write(findSum(arr, N));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// JavaScript program to find
// the sum of all minimum
// occurring elements in an array
// Function to find the sum of all minimum
// 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);
}
}
// Find the min frequency
let minFreq = Number.MAX_VALUE;
for (let [key, value] of mp.entries())
{
if (value < minFreq)
{
minFreq = value;
}
}
// Traverse the map again and find the sum
let sum = 0;
for (let [key, value] of mp.entries())
{
if (value == minFreq)
{
sum += key * value;
}
}
return sum;
}
// Driver Code
let arr=[ 10, 20, 30, 40, 40 ];
let N = arr.length;
document.write(findSum(arr, N));
// This code is contributed by patel2127
</script>
Producción:
60
Complejidad de tiempo : O(N), donde N es el número de elementos en la array.