# Smallest Element Repeated Exactly K Times  Difficulty Level Medium
Frequently asked in Belzabar Komli Media Netskope Nvidia Opera ServiceNow UHG Optum
Array Hash String

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.

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

1. Initialize a variable ‘flag’ with false. Flag denotes if we have found any element with frequency K or not.
2. Run a loop for I in range 0 to n-1
1. Initialize a variable count with zero which will count the frequency of A[i] in the array.
2. Run a loop for j in range 0 to n-1
1. If A[j] is equal to A[i], increment count by 1.
3. If count is equal to K, update the ans=min(ans,A[i]).
3. Check, If the flag is true then print the ans, otherwise print that there is no element with frequency K.
Find Words That Can Be Formed by Characters Leetcode Solution

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

Count Pairs With Given Sum

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

1. Store the frequency if each element in a hash table.
2. Initialize a variable ‘flag’ with false. Flag denotes if we have found any element with frequency K or not.
3. Iterate the hash table and find the smallest element with frequency K.
4. 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).

Change the Array into Permutation of Numbers From 1 to 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).

References 