Suma de todos los elementos que se repiten ‘k’ veces en una array

Dada una array, tenemos que encontrar la suma de todos los elementos que se repiten k veces en una array. Necesitamos considerar cada elemento repetitivo solo una vez en la suma.
Ejemplos: 
 

Input : arr[] = {2, 3, 9, 9}
            k = 1
Output : 5
2 + 3 = 5

Input : arr[] = {9, 8, 8, 8, 10, 4}
          k = 3
Output : 8

Una solución simple es usar dos bucles anidados para contar las ocurrencias de cada elemento. Mientras contamos, debemos considerar un elemento solo si aún no se ha considerado.
 

// C++ program find sum of elements that
// appear k times.
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the sum
int sumKRepeating(int arr[], int n, int k)
{
    int sum = 0;
 
    // To keep track of processed elements
    vector<bool> visited(n, false);
 
    // initializing count equal to zero
    for (int i = 0; i < n; i++) {
 
        // If arr[i] already processed
        if (visited[i] == true)
            continue;
 
        // counting occurrences of arr[i]
        int count = 1;
        for (int j = i + 1; j < n; j++) {           
            if (arr[i] == arr[j]) {
                count++;
                visited[j] = true;
            }
        }
   
        if (count == k)
           sum += arr[i];
    }
 
    return sum;
}
 
// Driver code
int main()
{
    int arr[] = { 9, 9, 10, 11, 8, 8, 9, 8 };
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 3;
    cout << sumKRepeating(arr, n, k);
    return 0;
}

// Java program find sum of
// elements that appear k times.
import java.util.*;
 
class GFG
{
// Function to count the sum
static int sumKRepeating(int arr[],
                         int n, int k)
{
    int sum = 0;
 
    // To keep track of
    // processed elements
    Vector<Boolean> visited = new Vector<Boolean>();
     
    for (int i = 0; i < n; i++)
    visited.add(false);
 
    // initializing count
    // equal to zero
    for (int i = 0; i < n; i++)
    {
 
        // If arr[i] already processed
        if (visited.get(i) == true)
            continue;
 
        // counting occurrences of arr[i]
        int count = 1;
        for (int j = i + 1; j < n; j++)
        {        
            if (arr[i] == arr[j])
            {
                count++;
                visited.add(j, true);
            }
        }
 
        if (count == k)
        sum += arr[i];
    }
 
    return sum;
}
 
// Driver code
public static void main(String args[])
{
    int arr[] = { 9, 9, 10, 11,
                  8, 8, 9, 8 };
    int n = arr.length;
    int k = 3;
    System.out.println(sumKRepeating(arr, n, k));
}
}
 
// This code is contributed by Arnab Kundu

# Python 3 program find sum of elements
# that appear k times.
 
# Function to count the sum
def sumKRepeating(arr, n, k):
    sum = 0
 
    # To keep track of processed elements
    visited = [False for i in range(n)]
 
    # initializing count equal to zero
    for i in range(0, n, 1):
         
        # If arr[i] already processed
        if (visited[i] == True):
            continue
 
        # counting occurrences of arr[i]
        count = 1
        for j in range(i + 1, n, 1):
            if (arr[i] == arr[j]):
                count += 1
                visited[j] = True
     
        if (count == k):
            sum += arr[i]
 
    return sum
 
# Driver code
if __name__ == '__main__':
    arr = [9, 9, 10, 11, 8, 8, 9, 8]
    n = len(arr)
    k = 3
    print(sumKRepeating(arr, n, k))
 
# This code is contributed by
# Shashank_Sharma

// c# program find sum of
// elements that appear k times.
using System;
using System.Collections.Generic;
 
class GFG
{
// Function to count the sum
public static int sumKRepeating(int[] arr,
                                int n, int k)
{
    int sum = 0;
 
    // To keep track of
    // processed elements
    List<bool> visited = new List<bool>();
 
    for (int i = 0; i < n; i++)
    {
        visited.Add(false);
    }
 
    // initializing count
    // equal to zero
    for (int i = 0; i < n; i++)
    {
 
        // If arr[i] already processed
        if (visited[i] == true)
        {
            continue;
        }
 
        // counting occurrences of arr[i]
        int count = 1;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[i] == arr[j])
            {
                count++;
                visited.Insert(j, true);
            }
        }
 
        if (count == k)
        {
            sum += arr[i];
        }
    }
 
    return sum;
}
 
// Driver code
public static void Main(string[] args)
{
    int[] arr = new int[] {9, 9, 10, 11,
                           8, 8, 9, 8};
    int n = arr.Length;
    int k = 3;
    Console.WriteLine(sumKRepeating(arr, n, k));
}
}
 
// This code is contributed
// by Shrikant13

<script>
// Javascript program find sum of
// elements that appear k times.
 
// Function to count the sum
function sumKRepeating(arr,n,k)
{
    let sum = 0;
   
    // To keep track of
    // processed elements
    let visited = [];
       
    for (let i = 0; i < n; i++)
        visited.push(false);
   
    // initializing count
    // equal to zero
    for (let i = 0; i < n; i++)
    {
   
        // If arr[i] already processed
        if (visited[i] == true)
            continue;
   
        // counting occurrences of arr[i]
        let count = 1;
        for (let j = i + 1; j < n; j++)
        {        
            if (arr[i] == arr[j])
            {
                count++;
                visited[j]= true;
            }
        }
   
        if (count == k)
            sum += arr[i];
    }
   
    return sum;
}
 
// Driver code
let arr=[9, 9, 10, 11,
                  8, 8, 9, 8 ];
                   
let n = arr.length;
let k = 3;
document.write(sumKRepeating(arr, n, k));
 
// This code is contributed by patel2127
</script>

17

Complejidad de tiempo: O(n*n) 
Espacio auxiliar: O(n)
Una solución eficiente es utilizar hashing. Contamos las frecuencias de todos los elementos. Luego recorremos la tabla hash y sumamos aquellos elementos cuyo recuento de ocurrencias es k. 
 

// C++ program find sum of elements that
// appear k times.
#include <bits/stdc++.h>
using namespace std;
 
// Returns sum of k appearing elements.
int sumKRepeating(int arr[], int n, int k)
{
   int sum = 0;
 
   // Count frequencies of all items
   unordered_map<int, int> mp;
   for (int i=0; i<n; i++)
      mp[arr[i]]++;
 
   // Sum items with frequencies equal to k.
   for (auto x : mp)
     if (x.second == k)
        sum += x.first;
   return sum;
}
 
// Driver code
int main()
{
    int arr[] = { 9, 9, 10, 11, 8, 8, 9, 8 };
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 3;
    cout << sumKRepeating(arr, n, k);
    return 0;
}

// Java program find sum of
// elements that appear k times.
import java.util.HashMap;
import java.util.Map;
 
class GfG
{
 
    // Returns sum of k appearing elements.
    static int sumKRepeating(int arr[], int n, int k)
    {
        int sum = 0;
         
        // Count frequencies of all items
        HashMap<Integer, Integer> mp = new HashMap<>();
        for (int i=0; i<n; i++)
        {
            if (!mp.containsKey(arr[i]))
                mp.put(arr[i], 0);
            mp.put(arr[i], mp.get(arr[i]) + 1);
        }
         
        // Sum items with frequencies equal to k.
        for (Integer x : mp.keySet())
            if (mp.get(x) == k)
                sum += x;
        return sum;
    }
 
    // Driver code
    public static void main(String []args)
    {
         
        int arr[] = { 9, 9, 10, 11, 8, 8, 9, 8 };
        int n = arr.length;
        int k = 3;
 
        System.out.println(sumKRepeating(arr, n, k));
    }
}
 
// This code is contributed by Rituraj Jain

# Python3 program find Sum of elements
# that appear k times.
import math as mt
 
# Returns Sum of k appearing elements.
def sumKRepeating(arr, n, k):
    Sum = 0
 
# Count frequencies of all items
    mp = dict()
    for i in range(n):
        if arr[i] in mp.keys():
            mp[arr[i]] += 1
        else:
            mp[arr[i]] = 1
                 
# Sum items with frequencies equal to k.
    for x in mp:
        if (mp[x] == k):
            Sum += x
    return Sum
 
# Driver code
arr = [ 9, 9, 10, 11, 8, 8, 9, 8 ]
n = len(arr)
k = 3
print(sumKRepeating(arr, n, k))
 
# This code is contributed
# by Mohit kumar 29

// C# program find sum of
// elements that appear k times.
using System;
using System.Collections.Generic;
class GfG
{
 
    // Returns sum of k appearing elements.
    static int sumKRepeating(int []arr, int n, int k)
    {
        int sum = 0;
         
        // Count frequencies of all items
        Dictionary<int,int> mp = new Dictionary<int,int>();
        for (int i = 0 ; i < n; i++)
        {
            if(mp.ContainsKey(arr[i]))
            {
                var val = mp[arr[i]];
                mp.Remove(arr[i]);
                mp.Add(arr[i], val + 1);
            }
            else
            {
                mp.Add(arr[i], 1);
            }
        }
        // Sum items with frequencies equal to k.
        foreach(KeyValuePair<int, int> entry in mp)
        {
            if(entry.Value >= k)
            {
                sum += entry.Key;
            }
        }
        return sum;
    }
 
    // Driver code
    public static void Main(String []args)
    {
         
        int []arr = { 9, 9, 10, 11, 8, 8, 9, 8 };
        int n = arr.Length;
        int k = 3;
 
        Console.WriteLine(sumKRepeating(arr, n, k));
    }
}
 
// This code contributed by Rajput-Ji

<script>
 
// JavaScript program find sum of
// elements that appear k times.
 
// Returns sum of k appearing elements.
function sumKRepeating(arr,n,k)
{
    let sum = 0;
          
        // Count frequencies of all items
        let mp = new Map();
        for (let i=0; i<n; i++)
        {
            if (!mp.has(arr[i]))
                mp.set(arr[i], 0);
            mp.set(arr[i], mp.get(arr[i]) + 1);
        }
          
        // Sum items with frequencies equal to k.
        for (let [key, value] of mp.entries())
            if (mp.get(key) == k)
                sum += key;
        return sum;
}
 
// Driver code
let arr=[9, 9, 10, 11, 8, 8, 9, 8];
let n = arr.length;
let k = 3;
document.write(sumKRepeating(arr, n, k));
 
 
// This code is contributed by unknown2108
 
</script>

17

Tiempo Complejidad : O(n) 
Espacio Auxiliar : O(n)