Finding the First Element Occurring K Times

Let's start by understanding the problem statement of this task.

You are given an array, your work is to find the element which occurs exactly k times in a given array.

Hint:

For printing the number in an array which occurs k times can be done by storing the frequency of each integer and print the integer whose frequency occurs exactly k times in the array in less time complexity.

Quick Think:

For solving the above algorithm, we need to ponder over the following points:

• Store the frequency of each element in the array in an unordered map.
• If the frequency matches the count of that particular integer, then print out the element.

Algorithm:

Create a function to find the frequency of the elements in the array with arguments as the array the size of the array and the count of the number of times the element occurs and follow the following steps:-

Step1: Traverse the array and keep pushing the frequency of each element in the map.

Step2: Now, check if the count of the given element in the map is equal to the frequency given, then print out the element else continue.

Step3: If the element is not found in the array, then return -1.

Implementation Of The Above Algorithm:

Now let's see the implementation of the above algorithm,

#include <bits/stdc++.h>
using namespace std;

/*function to find the first element
occurring k number of times. */
int firstElement(int arr[], int n, int k)
{
	unordered_map<int, int> count_map;
	for (int i = 0; i < n; i++)
		count_map[arr[i]]++;

	for (int i = 0; i < n; i++)
		/*if count of element == k ,then
		it is the required first element. */
		if (count_map[arr[i]] == k)
			return arr[i];
	return -1;
}

// Driver program to test above algorithm. */
int main()
{
	int arr[] = { 1, 7, 4, 3, 4, 8, 7 };

	int n = sizeof(arr) / sizeof(arr[0]);
	int k = 2;
	cout << firstElement(arr, n, k);
	return 0;
}

The time complexity of the above algorithm is O(n).

The output of the above algorithm is 7.

Explanation Of The Above Algorithm:

Let us consider an array as shown in the above diagram and follow the step to understand the algorithm.

• The frequency of all the elements in the array is pushed as shown in the diagram above.
• Now, traversing the array we find the first element as 1, now since the frequency of the element is 1, hence we move to the next array element.

• Now, the next array element is 7 since the frequency of the element is 2 so, we output the result as shown in the diagram above.