Last Updated on March 30, 2022 by Ria Pathak
CONCEPTS USED:
Hashing
DIFFICULTY LEVEL:
Easy
PROBLEM STATEMENT(SIMPLIFIED):
Given an array
AwithNintegers and an integerK, print the smallest number in the array which occurs exactlyKtimes.
See original problem statement here
For Example:
Input : N = 5, K = 2
arr[] = [2, 2, 1, 3, 1]
Output : 1 (both 1 & 2 occurs 2 times but 1 < 2)SOLVING APPROACH:
- Store the frequency of all elements in a temporary
hash array.- Traverse the
hash arrayfrom(1to Size of Hash array)and whenever the frequency of an element matches withK, print it and return.
SOLUTIONS:
#include <stdio.h>
int main()
{
int n, k; scanf("%d",&n);
int arr[n], hash[100001] = {0};
for(int i=0; i<n; i++){
scanf("%d",&arr[i]);
hash[arr[i]]++; //store the frequency of each element
}
scanf("%d",&k);
//finding the smallest element having frequency k
for(int i=0; i<100001; i++){
if(hash[i] == k){
printf("%d",i);
break;
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k; cin>>n;
int arr[n], hash[100001] = {0};
for(int i=0; i<n; i++){
cin>>arr[i];
hash[arr[i]]++; //store the frequency of each element
}
cin>>k;
//finding the smallest element having frequency k
for(int i=0; i<100001; i++){
if(hash[i] == k){
cout<<i;
break;
}
}
return 0;
}
import java.util.*;
import java.io.*;
public class Main {
public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
int hash[] = new int[100001];
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
hash[arr[i]]++; //store the frequency of each element
}
int k = sc.nextInt();
//finding the smallest element having frequency k
for(int i=0; i<100001; i++){
if(hash[i] == k){
System.out.print(i);
break;
}
}
}
}
[forminator_quiz id="1662"]
Space Complexity: O(N), due to additional hash array.
This article tried to discuss the concept of hashing. Hope this blog helps you understand and solve the problem. To practice more problems on hashing you can check out MYCODE | Competitive Programming.