Given an array, we have to find the sum of all the elements repeating k times in an array. We need to consider every repeating element just once in the sum.
Examples:
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
One simple solution is to use two nested loops to count the occurrences of every element. While counting, we need to consider an element only if it is not already considered.
Implementation:
C++
// C++ program find sum of elements that// appear k times. #include <bits/stdc++.h>using namespace std;// Function to count the sumint 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 codeint 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
// Java program find sum of // elements that appear k times. import java.util.*;class GFG{// Function to count the sumstatic 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 codepublic 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 |
Python3
# Python 3 program find sum of elements # that appear k times. # Function to count the sumdef 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 codeif __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#
// 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 |
Javascript
<script>// Javascript program find sum of // elements that appear k times. // Function to count the sumfunction 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 codelet 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> |
Output
17
Complexity Analysis:
- Time Complexity : O(n*n)
- Auxiliary Space : O(n)
An efficient solution is to use hashing. We count frequencies of all items. Then we traverse hash table and sum those items whose count of occurrences is k.
Implementation:
C++
// 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 codeint 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
// 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
# 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 codearr = [ 9, 9, 10, 11, 8, 8, 9, 8 ]n = len(arr)k = 3print(sumKRepeating(arr, n, k))# This code is contributed # by Mohit kumar 29 |
C#
// 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 |
Javascript
<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 codelet 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> |
Output
17
Complexity Analysis
- Time Complexity : O(n)
- Auxiliary Space : O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
