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

Please click Like if you loved this article?

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.
See also
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.

See also
Count Pairs With Given Sum

After that, we can just traverse the hash table to find the smallest element with frequency exactly K.

Please click Like if you loved this article?

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 TimesPin

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

See also
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

Please click Like if you loved this article?

Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh