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. With reference to competitive programming course online, 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;
      } 
    }
  }
}

Space Complexity: O(N), due to additional hash array.

Previous post Small Count
Next post Next Greater Same Digit

Leave a Reply

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