Given an array which may contain duplicates, print all elements and their frequencies.
Examples:
Input : arr[] = {10, 20, 20, 10, 10, 20, 5, 20}
Output : 10 3
20 4
5 1
Input : arr[] = {10, 20, 20}
Output : 10 1
20 2
A simple solution is to run two loops. For every item count number of times, it occurs. To avoid duplicate printing, keep track of processed items.
Implementation:
C++
// CPP program to count frequencies of array items#include <bits/stdc++.h>using namespace std;void countFreq(int arr[], int n){ // Mark all array elements as not visited vector<bool> visited(n, false); // Traverse through array elements and // count frequencies for (int i = 0; i < n; i++) { // Skip this element if already processed if (visited[i] == true) continue; // Count frequency int count = 1; for (int j = i + 1; j < n; j++) { if (arr[i] == arr[j]) { visited[j] = true; count++; } } cout << arr[i] << " " << count << endl; }}int main(){ int arr[] = { 10, 20, 20, 10, 10, 20, 5, 20 }; int n = sizeof(arr) / sizeof(arr[0]); countFreq(arr, n); return 0;} |
Java
// Java program to count frequencies of array itemsimport java.util.Arrays;class GFG{public static void countFreq(int arr[], int n){ boolean visited[] = new boolean[n]; Arrays.fill(visited, false); // Traverse through array elements and // count frequencies for (int i = 0; i < n; i++) { // Skip this element if already processed if (visited[i] == true) continue; // Count frequency int count = 1; for (int j = i + 1; j < n; j++) { if (arr[i] == arr[j]) { visited[j] = true; count++; } } System.out.println(arr[i] + " " + count); }}// Driver codepublic static void main(String []args){ int arr[] = new int[]{ 10, 20, 20, 10, 10, 20, 5, 20 }; int n = arr.length; countFreq(arr, n);}}// This code contributed by Adarsh_Verma. |
Python3
# Python 3 program to count frequencies# of array itemsdef countFreq(arr, n): # Mark all array elements as not visited visited = [False for i in range(n)] # Traverse through array elements # and count frequencies for i in range(n): # Skip this element if already # processed if (visited[i] == True): continue # Count frequency count = 1 for j in range(i + 1, n, 1): if (arr[i] == arr[j]): visited[j] = True count += 1 print(arr[i], count)# Driver Codeif __name__ == '__main__': arr = [10, 20, 20, 10, 10, 20, 5, 20] n = len(arr) countFreq(arr, n) # This code is contributed by# Shashank_Sharma |
C#
// C# program to count frequencies of array itemsusing System;class GFG{ public static void countFreq(int []arr, int n) { bool []visited = new bool[n]; // Traverse through array elements and // count frequencies for (int i = 0; i < n; i++) { // Skip this element if already processed if (visited[i] == true) continue; // Count frequency int count = 1; for (int j = i + 1; j < n; j++) { if (arr[i] == arr[j]) { visited[j] = true; count++; } } Console.WriteLine(arr[i] + " " + count); } } // Driver code public static void Main(String []args) { int []arr = new int[]{ 10, 20, 20, 10, 10, 20, 5, 20 }; int n = arr.Length; countFreq(arr, n); }}// This code has been contributed by 29AjayKumar |
Javascript
<script>// JavaScript program to count frequencies of array itemsfunction countFreq(arr, n){ let visited = Array.from({length: n}, (_, i) => false); // Traverse through array elements and // count frequencies for (let i = 0; i < n; i++) { // Skip this element if already processed if (visited[i] == true) continue; // Count frequency let count = 1; for (let j = i + 1; j < n; j++) { if (arr[i] == arr[j]) { visited[j] = true; count++; } } document.write(arr[i] + " " + count + "<br/>"); }}// Driver Code let arr = [ 10, 20, 20, 10, 10, 20, 5, 20 ]; let n = arr.length; countFreq(arr, n); </script> |
Output
10 3 20 4 5 1
Complexity Analysis:
- Time Complexity : O(n2)
- Auxiliary Space : O(n)
An efficient solution is to use hashing.
Implementation:
C++
// CPP program to count frequencies of array items#include <bits/stdc++.h>using namespace std;void countFreq(int arr[], int n){ unordered_map<int, int> mp; // Traverse through array elements and // count frequencies for (int i = 0; i < n; i++) mp[arr[i]]++; // Traverse through map and print frequencies for (auto x : mp) cout << x.first << " " << x.second << endl;}int main(){ int arr[] = { 10, 20, 20, 10, 10, 20, 5, 20 }; int n = sizeof(arr) / sizeof(arr[0]); countFreq(arr, n); return 0;} |
Java
// Java program to count frequencies of array itemsimport java.util.*;class GFG{ static void countFreq(int arr[], int n) { Map<Integer, Integer> mp = new HashMap<>(); // Traverse through array elements and // count frequencies for (int i = 0; i < n; i++) { if (mp.containsKey(arr[i])) { mp.put(arr[i], mp.get(arr[i]) + 1); } else { mp.put(arr[i], 1); } } // Traverse through map and print frequencies for (Map.Entry<Integer, Integer> entry : mp.entrySet()) { System.out.println(entry.getKey() + " " + entry.getValue()); } } // Driver code public static void main(String args[]) { int arr[] = {10, 20, 20, 10, 10, 20, 5, 20}; int n = arr.length; countFreq(arr, n); }}// This code contributed by Rajput-Ji |
Python3
# Python3 program to count frequencies # of array itemsdef countFreq(arr, n): mp = dict() # Traverse through array elements # and count frequencies for i in range(n): if arr[i] in mp.keys(): mp[arr[i]] += 1 else: mp[arr[i]] = 1 # Traverse through map and print # frequencies for x in mp: print(x, " ", mp[x])# Driver codearr = [10, 20, 20, 10, 10, 20, 5, 20 ]n = len(arr)countFreq(arr, n)# This code is contributed by # Mohit kumar 29 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic; class GFG{ static void countFreq(int []arr, int n) { Dictionary<int, int> mp = new Dictionary<int,int>(); // Traverse through array elements and // count frequencies 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); } } // Traverse through map and print frequencies foreach(KeyValuePair<int, int> entry in mp) { Console.WriteLine(entry.Key + " " + entry.Value); } } // Driver code public static void Main(String []args) { int []arr = {10, 20, 20, 10, 10, 20, 5, 20}; int n = arr.Length; countFreq(arr, n); }}/* This code contributed by PrinciRaj1992 */ |
Javascript
<script>// JavaScript program to count // frequencies of array itemsfunction countFreq(arr, n){ const map ={} // Traverse through array elements and // count frequencies for (let i = 0; i < n; i++) { if(map[arr[i]){ map[arr[i]]+=1 } else{ map[arr[i]] =1 } } console.log(map)}var arr = [10, 20, 20, 10, 10, 20, 5, 20];var n = arr.length;countFreq(arr, n);</script> |
Output
5 1 20 4 10 3
Complexity Analysis:
- Time Complexity : O(n)
- Auxiliary Space : O(n)
In the above efficient solution, how to print elements in same order as they appear in input?
Implementation:
C++
// CPP program to count frequencies of array items#include <bits/stdc++.h>using namespace std;void countFreq(int arr[], int n){ unordered_map<int, int> mp; // Traverse through array elements and // count frequencies for (int i = 0; i < n; i++) mp[arr[i]]++; // To print elements according to first // occurrence, traverse array one more time // print frequencies of elements and mark // frequencies as -1 so that same element // is not printed multiple times. for (int i = 0; i < n; i++) { if (mp[arr[i]] != -1) { cout << arr[i] << " " << mp[arr[i]] << endl; mp[arr[i]] = -1; } }}int main(){ int arr[] = { 10, 20, 20, 10, 10, 20, 5, 20 }; int n = sizeof(arr) / sizeof(arr[0]); countFreq(arr, n); return 0;} |
Java
// Java program to count frequencies of array items import java.util.*;class GFG { static void countFreq(int arr[], int n) { Map<Integer, Integer> mp = new HashMap<>(); // Traverse through array elements and // count frequencies for (int i = 0; i < n; i++) { mp.put(arr[i], mp.get(arr[i]) == null ? 1 : mp.get(arr[i]) + 1); } // To print elements according to first // occurrence, traverse array one more time // print frequencies of elements and mark // frequencies as -1 so that same element // is not printed multiple times. for (int i = 0; i < n; i++) { if (mp.get(arr[i]) != -1) { System.out.println(arr[i] + " " + mp.get(arr[i])); mp.put(arr[i], -1); } } } // Driver code public static void main(String[] args) { int arr[] = {10, 20, 20, 10, 10, 20, 5, 20}; int n = arr.length; countFreq(arr, n); }}// This code contributed by Rajput-Ji |
Python3
# Python3 program to count frequencies of array itemsdef countFreq(arr, n): mp = {} # Traverse through array elements and # count frequencies for i in range(n): if arr[i] not in mp: mp[arr[i]] = 0 mp[arr[i]] += 1 # To print elements according to first # occurrence, traverse array one more time # print frequencies of elements and mark # frequencies as -1 so that same element # is not printed multiple times. for i in range(n): if (mp[arr[i]] != -1): print(arr[i],mp[arr[i]]) mp[arr[i]] = -1# Driver codearr = [10, 20, 20, 10, 10, 20, 5, 20]n = len(arr)countFreq(arr, n)# This code is contributed by shubhamsingh10 |
C#
// C# program to count frequencies of array items using System;using System.Collections.Generic;class GFG { static void countFreq(int []arr, int n) { Dictionary<int,int> mp = new Dictionary<int,int>(); // Traverse through array elements and // count frequencies 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); } } // To print elements according to first // occurrence, traverse array one more time // print frequencies of elements and mark // frequencies as -1 so that same element // is not printed multiple times. for (int i = 0; i < n; i++) { if (mp.ContainsKey(arr[i]) && mp[arr[i]] != -1) { Console.WriteLine(arr[i] + " " + mp[arr[i]]); mp.Remove(arr[i]); mp.Add(arr[i], -1); } } } // Driver code public static void Main(String[] args) { int []arr = {10, 20, 20, 10, 10, 20, 5, 20}; int n = arr.Length; countFreq(arr, n); } } // This code is contributed by Princi Singh |
Javascript
<script>// Javascript program to count frequencies of array itemsfunction countFreq(arr, n){ var mp = new Map(); // Traverse through array elements and // count frequencies for (var 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) } // To print elements according to first // occurrence, traverse array one more time // print frequencies of elements and mark // frequencies as -1 so that same element // is not printed multiple times. for (var i = 0; i < n; i++) { if (mp.get(arr[i]) != -1) { document.write( arr[i] + " " + mp.get(arr[i]) + "<br>"); mp.set(arr[i], -1); } }}var arr = [10, 20, 20, 10, 10, 20, 5, 20];var n = arr.length;countFreq(arr, n);// This code is contributed by rrrtnx.</script> |
Output
10 3 20 4 5 1
Complexity Analysis:
- Time Complexity : O(n)
- Auxiliary Space : O(n)
This problem can be solved in Java using Hashmap. Below is the program.
Implementation:
C++
// C++ program to count frequencies of// integers in array using Hashmap#include <bits/stdc++.h>using namespace std;void frequencyNumber(int arr[],int size){ // Creating a HashMap containing integer // as a key and occurrences as a value unordered_map<int,int>freqMap; for (int i=0;i<size;i++) { freqMap[arr[i]]++; } // Printing the freqMap for (auto it : freqMap) { cout<<it.first<<" "<<it.second<<endl; }}int main(){ int arr[] = {10, 20, 20, 10, 10, 20, 5, 20}; int size = sizeof(arr)/sizeof(arr[0]); frequencyNumber(arr,size);}// This code is contributed by shinjanpatra. |
Java
// Java program to count frequencies of// integers in array using Hashmapimport java.io.*;import java.util.*;class OccurenceOfNumberInArray { static void frequencyNumber(int arr[], int size) { // Creating a HashMap containing integer // as a key and occurrences as a value HashMap<Integer, Integer> freqMap = new HashMap<Integer, Integer>(); for (int i=0;i<size;i++) { if (freqMap.containsKey(arr[i])) { // If number is present in freqMap, // incrementing it's count by 1 freqMap.put(arr[i], freqMap.get(arr[i]) + 1); } else { // If integer is not present in freqMap, // putting this integer to freqMap with 1 as it's value freqMap.put(arr[i], 1); } } // Printing the freqMap for (Map.Entry entry : freqMap.entrySet()) { System.out.println(entry.getKey() + " " + entry.getValue()); } } // Driver Code public static void main(String[] args) { int arr[] = {10, 20, 20, 10, 10, 20, 5, 20}; int size = arr.length; frequencyNumber(arr,size); }} |
Python3
# Python program to count frequencies of# integers in array using Hashmapdef frequencyNumber(arr,size): # Creating a HashMap containing integer # as a key and occurrences as a value freqMap = {} for i in range(size): if (arr[i] in freqMap): # If number is present in freqMap, # incrementing it's count by 1 freqMap[arr[i]] = freqMap[arr[i]] + 1 else: # If integer is not present in freqMap, # putting this integer to freqMap with 1 as it's value freqMap[arr[i]] = 1 # Printing the freqMap for key, value in freqMap.items(): print(f"{key} {value}")# Driver Codearr = [10, 20, 20, 10, 10, 20, 5, 20]size = len(arr)frequencyNumber(arr,size)# This code is contributed by shinjanpatra |
C#
// C# program to count frequencies of// integers in array using Hashmapusing System;using System.Collections.Generic; class GFG{ static void frequencyNumber(int []arr,int size) { // Creating a Dictionary containing integer // as a key and occurrences as a value Dictionary<int, int> freqMap = new Dictionary<int,int>(); for(int i = 0; i < size; i++){ if (freqMap.ContainsKey(arr[i])) { var val = freqMap[arr[i]]; freqMap.Remove(arr[i]); freqMap.Add(arr[i], val + 1); } else { freqMap.Add(arr[i], 1); } } // Printing the freqMap foreach(KeyValuePair<int, int> entry in freqMap) { Console.WriteLine(entry.Key + " " + entry.Value); } } public static void Main(String []args) { int []arr = {10, 20, 20, 10, 10, 20, 5, 20}; int size = arr.Length; frequencyNumber(arr,size); }}// This code is contributed by Taranpreet |
Javascript
<script>// Javascript program to count frequencies of// integers in array using Hashmapfunction frequencyNumber(arr,size){ // Creating a HashMap containing integer // as a key and occurrences as a value let freqMap = new Map(); for (let i=0;i<size;i++) { if (freqMap.has(arr[i])) { // If number is present in freqMap, // incrementing it's count by 1 freqMap.set(arr[i], freqMap.get(arr[i]) + 1); } else { // If integer is not present in freqMap, // putting this integer to freqMap with 1 as it's value freqMap.set(arr[i], 1); } } // Printing the freqMap for (let [key, value] of freqMap.entries()) { document.write(key + " " + value+"<br>"); }}// Driver Codelet arr=[10, 20, 20, 10, 10, 20, 5, 20];let size = arr.length;frequencyNumber(arr,size);// This code is contributed by patel2127</script> |
Output
5 1 20 4 10 3
Complexity Analysis:
- Time Complexity: O(n) since using a single loop to track frequency
- Auxiliary Space: O(n) for hashmap.
Another Efficient Solution (Space optimization): we can find frequency of array elements using Binary search function . First we will sort the array for binary search . Our frequency of element will be ‘(last occ – first occ)+1’ of a element in a array .
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;//Function to find frequency of elements in the arrayvoid countFreq(int arr[], int n){ sort(arr,arr+n);//sort array for binary search for(int i = 0 ; i < n ;i++) { //index of first and last occ of arr[i] int first_index = lower_bound(arr,arr+n,arr[i])- arr; int last_index = upper_bound(arr,arr+n,arr[i])- arr-1; i=last_index; int fre=last_index-first_index+1;//finding frequency cout << arr[i] <<" "<<fre <<endl;//printing frequency } }// Drive codeint main(){ int arr[] = { 10, 20, 20, 10, 10, 20, 5, 20 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call countFreq(arr, n); return 0; }// This Code is contributed by nikhilsainiofficial546 |
Java
// Java program to count frequencies of// integers in array using Hashmapimport java.io.*;import java.util.*;class OccurenceOfNumberInArray { public static void countFreq(int[] arr, int n) { Arrays.sort(arr); //sort array for binary search for (int i = 0; i < n; i++) { //index of first and last occ of arr[i] int first_index = Arrays.binarySearch(arr, arr[i]); int last_index = Arrays.binarySearch(arr, arr[i]); while (first_index > 0 && arr[first_index - 1] == arr[i]) { first_index--; } while (last_index < n - 1 && arr[last_index + 1] == arr[i]) { last_index++; } i = last_index; int fre = last_index - first_index + 1;//finding frequency System.out.println(arr[i] + " " + fre);//printing frequency }} // Driver Code public static void main(String[] args) { int arr[] = {10, 20, 20, 10, 10, 20, 5, 20}; int size = arr.length; countFreq(arr,size); }} |
Python3
from bisect import bisect_left, bisect_right# Function to find frequency of elements in the arraydef countFreq(arr, n): arr.sort() # sort array for binary search i = 0 while i < n: # index of first and last occ of arr[i] first_index = bisect_left(arr, arr[i]) last_index = bisect_right(arr, arr[i]) - 1 i = last_index + 1 fre = last_index - first_index + 1 # finding frequency print(arr[i - 1], fre) # printing frequency# Driver codearr = [10, 20, 20, 10, 10, 20, 5, 20]n = len(arr)countFreq(arr, n) |
C#
using System;public class GFG { // Function to find frequency of elements in the array public static void countFreq(int[] arr, int n) { Array.Sort(arr); // sort array for binary search for (int i = 0; i < n; i++) { // index of first and last occurrence of arr[i] int first_index = Array.IndexOf(arr, arr[i]); int last_index = Array.LastIndexOf(arr, arr[i]); int fre = last_index - first_index + 1; // finding frequency Console.WriteLine(arr[i] + " " + fre); // printing frequency i = last_index; } } // Driver code static public void Main () { int[] arr = { 10, 20, 20, 10, 10, 20, 5, 20 }; int n = arr.Length; // Function call countFreq(arr, n); }} |
Javascript
// Javascript implementation of the above approach//Function to find frequency of elements in the arrayfunction countFreq(arr,n) { arr.sort((a, b) => a - b); //sort array for binary search let i = 0; while (i < n) { //index of first and last occ of arr[i] const first_index = arr.indexOf(arr[i]); const last_index = arr.lastIndexOf(arr[i]); i = last_index; const fre = last_index - first_index + 1; //finding frequency console.log(arr[i], fre); //printing frequency i++; }}// Driver codeconst arr = [ 10, 20, 20, 10, 10, 20, 5, 20 ];countFreq(arr,arr.length); |
Output
5 1 10 3 20 4
Time Complexity: O(n*log2n) , where O(log2n) time for binary search function .
Auxiliary Space: O(1)
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!
