We are given an array A[] on size n. We have to find the smallest element that is repeated exactly k times in the array.
Table of Contents
Example
Input
A[]= {1, 2 ,2 ,5 ,5 ,2 ,5}
K=3
Output
Smallest element with frequency K is: 2
Approach 1: Brute force
Main idea
For every element in the array, we can find its frequency by traversing the whole array and if its frequency is equal to K, then we will take a minimum of our previous answer and this element. In the end, we will print our final answer.
Algorithm for finding Smallest Element Repeated Exactly K Times
- Initialize a variable ‘flag’ with false. Flag denotes if we have found any element with frequency K or not.
- Run a loop for I in range 0 to n-1
- Initialize a variable count with zero which will count the frequency of A[i] in the array.
- Run a loop for j in range 0 to n-1
- If A[j] is equal to A[i], increment count by 1.
- If count is equal to K, update the ans=min(ans,A[i]).
- Check, If the flag is true then print the ans, otherwise print that there is no element with frequency K.
Implementation
C++ program
#include <bits/stdc++.h>
using namespace std;
void smallestElementRepeatedExactlyKTimes(vector<int> A, int K)
{
int n = A.size();
bool flag = false;
int ans = 0;
for (int i = 0; i < n; i++)
{
int count = 0;
for (int j = 0; j < n; j++)
{
if (A[i] == A[j])
{
count++;
}
}
if (count == K)
{
if (flag == false)
{
flag = true;
ans = A[i];
}
else
{
ans = min(ans, A[i]);
}
}
}
if (flag == false)
{
cout << "There is no element with frequency K.";
}
else
{
cout << "Smallest element with frequency K is: " << ans;
}
return;
}
int main()
{
vector<int> A = {1, 2, 2, 5, 5, 2, 5};
int K = 3;
smallestElementRepeatedExactlyKTimes(A, K);
return 0;
}
Smallest element with frequency K is: 2
JAVA program
public class Main
{
static void smallestElementRepeatedExactlyKTimes(int A[],int K)
{
int n = A.length;
boolean flag = false;
int ans = 0;
for (int i = 0; i < n; i++)
{
int count = 0;
for (int j = 0; j < n; j++)
{
if (A[i] == A[j])
{
count++;
}
}
if (count == K)
{
if (flag == false)
{
flag = true;
ans = A[i];
}
else
{
ans = Math.min(ans, A[i]);
}
}
}
if (flag == false)
{
System.out.print("There is no element with frequency K.");
}
else
{
System.out.print("Smallest element with frequency K is: "+ ans);
}
return;
}
public static void main(String[] args) {
int A[] = {1, 2, 2, 5, 5, 2, 5};
int K = 3;
smallestElementRepeatedExactlyKTimes(A, K);
}
}
Smallest element with frequency K is: 2
Complexity Analysis for finding Smallest Element Repeated Exactly K Times
Time complexity
We are using two nested loops, both of size N. So the total time complexity is O(N^2).
Space complexity
We are using constant space. So space complexity is O(1).
Approach 2: Using hashing
Main idea
We can store the frequency of each element in a hash table.
After that, we can just traverse the hash table to find the smallest element with frequency exactly K.
Algorithm for finding Smallest Element Repeated Exactly K Times
- Store the frequency if each element in a hash table.
- Initialize a variable ‘flag’ with false. Flag denotes if we have found any element with frequency K or not.
- Iterate the hash table and find the smallest element with frequency K.
- If the flag is true then print the ans, otherwise print that there is no element with frequency K.
Understand with example
A[]= {1, 2 ,2 ,5 ,5 ,2 ,5}
K=3
For this array, the hash table will look like this:
Implementation
C++ program
#include <bits/stdc++.h>
using namespace std;
void smallestElementRepeatedExactlyKTimes(vector<int> A, int K)
{
int n = A.size();
bool flag = false;
int ans = 0;
unordered_map<int, int> hash_table;
for (int i = 0; i < n; i++)
{
hash_table[A[i]]++;
}
for (auto element : hash_table)
{
if (element.second == K)
{
if (flag == false)
{
flag = true;
ans = element.first;
}
else
{
ans = min(ans, element.first);
}
}
}
if (flag == false)
{
cout << "There is no element with frequency K.";
}
else
{
cout << "Smallest element with frequency K is: " << ans;
}
return;
}
int main()
{
vector<int> A = {1, 2, 2, 5, 5, 2, 5};
int K = 3;
smallestElementRepeatedExactlyKTimes(A, K);
return 0;
}
Smallest element with frequency K is: 2
JAVA program
import java.util.*;
public class Main
{
static void smallestElementRepeatedExactlyKTimes(int A[],int K)
{
int n = A.length;
boolean flag = false;
int ans = 0;
HashMap<Integer, Integer> hash_table = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i ++)
{
if (hash_table.containsKey(A[i]))
{
hash_table.put(A[i], hash_table.get(A[i]) + 1);
}
else{
hash_table.put(A[i], 1);
}
}
for(Map.Entry element: hash_table.entrySet())
{
if(((int)element.getValue()==K))
{
if(flag==false)
{
flag=true;
ans=((int)(element.getKey()));
}
else{
ans=Math.min(ans,((int)(element.getKey())));
}
}
}
if (flag == false)
{
System.out.print("There is no element with frequency K.");
}
else
{
System.out.print("Smallest element with frequency K is: "+ ans);
}
return;
}
public static void main(String[] args) {
int A[] = {1, 2, 2, 5, 5, 2, 5};
int K = 3;
smallestElementRepeatedExactlyKTimes(A, K);
}
}
Smallest element with frequency K is: 2
Complexity Analysis for finding Smallest Element Repeated Exactly K Times
Time complexity
We are traversing the array only once, so the time complexity is O(N).
Space complexity
We are maintaining a hash table to store the frequency of elements in the array so the space complexity is O(N).