Counting Frequencies of Array Elements in C++

We have an array of integer items with duplicate values, and our objective is to compute the frequencies of the different elements in the array.

Methods:

Methods that can be used to find out the frequencies of elements in an array in the C++ programming language.

Method 1: Naive technique (approach) with the extra-space method

Method 2: Naive technique (approach) without the extra-space method

Method 3: Using the sorting method

Method 4: Using the hash map method

1. Naive technique with the extra-space method

In this technique, using two "for" loops, we can count the frequency of every element.

1. Create an array of size "n" in order to see the status of the visited elements.
2. From index zero to n, execute a loop. If "visited[i] == 1," then that element is skipped.
3. Otherwise, make a "var count = 1" to retain the frequency count.
4. Execute a loop from the index "i+1" to "n."
5. If "arry[i] == arry[j]," then the count is increased by one and "visited[j]" is set to one.
6. After the "for" loop has finished iterating, print the element along with the count value.

Example

#include <bits/stdc++.h>
using namespace std;
/*  To run the program, use the main() function. */
int main() 
{ 
int arry[] = {100, 300, 100, 200, 100, 200, 300, 100}; 
    	int n = sizeof(arry)/sizeof(arry[0]); 
int visit[n];
for(int i=0; i<n; i++)
{
	if(visit[i]!=1)
	{
          	 		int count = 1;
           			for(int j=i+1; j<n; j++)
		{
		if(arry[i]==arry[j])
		{
                 				count++;
                 				visit[j]=1;
         				}
        			}
	 	cout<<arry[i]<<" is repeated "<<count<<" times "<<endl;
         		}
     	}
	return 0; 
}

Output:

Space Complexity and Time Complexity:

• Space Complexity: O(n)
• Time Complexity: O(n²)

2. Naive technique without the extra-space method

We will use the naive technique in this method to get the frequency of the elements in the supplied integer array without requiring any extra space.

Example

#include <bits/stdc++.h>
using namespace std;
void count_Frequency(int *arry, int size)
{
	for (int i = 0; i < size; i++)
	{
        		int flag = 0;
        		int count = 0;
		/* Any element's counting must be pushed to its most recent occurrence */
        		for (int j = i+1; j < size; j++)
		{
            		if (arry[i] == arry[j])	
			{
                			flag = 1;
                			break;
            		}
        		}
		/* The term "continue" is used to break the current iteration and proceeds to the following iteration in a "for" loop or a "while" loop */
        		if (flag == 1)
            		continue;
            
        		for(int j = 0;j<=i;j++)
		{
            		if(arry[i] == arry[j])
                		count +=1;
        		}
        
        		cout << arry[i] << ": " << count << endl;
    	}
}


int main()
{
   	int arry[] = {50, 80, 50, 70, 80, 100};
    	int size = sizeof(arry)/sizeof(arry[0]);
    	count_Frequency(arry, size);
	return 0;
}

Output:

Space Complexity and Time Complexity:

• Space Complexity: O(1)
• Time Complexity: O(n²)

3. Using the Sorting method

In this technique, we will sort the array and then count the frequency of the items.

Example

#include<bits/stdc++.h>
using namespace std;
void count_Distinct(int arry[], int n)
{
	sort(arry, arry + n);
 	// Traverse the sorted array
    	for (int i = 0; i < n; i++)
	{
        		int count = 1;
		/* When you come across duplicates, advance the index */
        		while (i < n - 1 && arry[i] == arry[i + 1])
		{
            		i++;
            		count++;
        		}
      	cout << arry[i] << ": " << count << endl;
    	}
}
 
/* Driver program for testing the above-mentioned function */
int main()
{
    	int arry[] = {50, 80, 50, 70, 80, 100};
    	int n = sizeof(arry) / sizeof(arry[0]);
    	count_Distinct(arry, n);
    	return 0;
}

Output:

Space Complexity and Time Complexity:

• Space Complexity: O(1)
• Time Complexity: O(nlogn)

4. Using the hash map method

In this technique, the frequency of the items will be stored using a hash-map approach.

1. Create an "unordered_map" with the name "ump."
2. Use a loop ("for" or "while") to iterate over the array.
3. Set “ump[arry[i]]++”
4. After finishing the iteration, execute a loop across map.
5. Also, print the key-value pair.

Example

#include <bits/stdc++.h>
using namespace std;
 void count_Freq(int arry[], int n)
{
   	unordered_map<int, int> ump;
 	/* Count frequencies as you traverse the array elements */
    	for (int i = 0; i < n; i++)
	{
        		ump[arry[i]]++;
	}
 
    	// Traverse through map and print frequencies
    	for (auto x : ump)
	{	
        		cout << x.first << " occurs " << x.second << endl;
	}
}
 int main()
{
   	int arry[] = { 101, 201, 201, 101, 101, 201, 51, 201 };
    	int n = sizeof(arry) / sizeof(arry[0]);
    	count_Freq(arry, n);
    	return 0;
}

Output: