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 !!