# Smallest element repeated exactly ‘k’ times (not limited to small range) in C++

In this tutorial, we are going to learn **how to find the smallest element repeated exactly ‘k’ times (not limited to small range) in C++**. Here, firstly we will see the algorithm to find the smallest element repeated exactly ‘k’ times in an array. After that, we will see the C++ program for the same.

We are given an array and a number ‘k’ and we have to find the smallest of an array that is repeated exactly ‘k’ times.

For Example:-

**Input:-** arr[ ]={1,2,7,1,8,3,1,2,7,4,4,1,6} and k=4

**Output:-** 1

**Input:-** arr[ ]={1,2,7,1,8,3,1,2,7,4,4,1,6} and k=2

**Output:-** 2

## Algorithm

To find the smallest element that is repeated exactly ‘k’ times, we are going to use hashmap (unordered_map). As we know hashmap is very efficient and find the frequency of each element in O(n) time. After finding frequency of each element we find the smallest number with exactly ‘k’ frequency.

**Steps:-
**

1. Initialize a unordered_map. 2. Traverse the given array and store the element and frequency in the unordered_map. 3. Traverse unordered_map and find the smallest number with exactly 'k' frequency. 4. return result.

## C++ program to find the smallest element repeated exactly ‘k’ times

So, here is the C++ implementation of the above algorithm:-

#include<bits/stdc++.h> using namespace std; /*==================================================== FUNCTION TO FIND THE SMALLEST ELEMENT REPEATED K TIMES =====================================================*/ int find_smallest(int arr[], int size, int k) { //Initializing hashmap unordered_map<int,int>umap; int ans=INT_MAX; //Travesrsing array and finding //frequency of each element for(int i=0;i<size;i++) { umap[arr[i]]++; } //Traversing map and finding smallest element //with exactly k frequency for(auto x:umap) { if(x.second==k) ans=min(ans,x.first); } if(ans!=INT_MAX) return ans; return -1; } /*====================================== MAIN FUNCTION =======================================*/ int main() { //Initialising variable k int k=4; //Initialising array arr int arr[]={1,2,7,1,8,3,1,2,7,4,4,1,6}; //Size of array int n=sizeof(arr)/sizeof(arr[0]); //Calling function find_smallest() int ans=find_smallest(arr,n,k); //Display Output cout<<"Smallest number repeated exactly k times is: " <<ans<<endl; return 0; }

**Output:-
**

Smallest number repeated exactly k times is: 1

**Time Complexity:- **O(n)

Thanks for reading this tutorial. I hope it helps you !!

## Leave a Reply