Smallest Element Repeated Exactly K Times

Difficulty Level Medium
Frequently asked in Belzabar Komli Media Netskope Nvidia Opera ServiceNow UHG Optum
Array Hash StringViews 3825

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.

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

  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:

Smallest Element Repeated Exactly K Times

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

References

Translate »