Dark Mode On/Off

LAST UPDATED: APRIL 24, 2023

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.

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.

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.

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.

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.**

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.

Advertisement