Smallest Number

CONCEPTS USED:

Hashing

DIFFICULTY LEVEL:

Easy

PROBLEM STATEMENT(SIMPLIFIED):

Given an array A with N integers and an integer K, print the smallest number in the array which occurs exactly K times.

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:

  1. Store the frequency of all elements in a temporary hash array.
  2. Traverse the hash array from (1 to Size of Hash array) and whenever the frequency of an element matches with K, 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.

Leave a Reply

Your email address will not be published. Required fields are marked *