First Element to Occur K Times in java

Given an array of ‘n’ integers. Print the first element that occurs k number of times. If there is no element that occurs for at least k number of times print -1.

Input Format

Line 1: contains two integers n and k.

Line 2: contains n-spaced integers denoting elements of the array.

Output Format

Print a single integer denoting the first element in the array which occurs at least k times. If no such element exists, print -1.

Example 1

Input

7 2
1 7 4 3 4 8 7

Output

4

Explanation

As we traverse the array the first number whose frequency becomes greater than or equal to k(2) is 4. Hence, the answer is 4.

Example 2

Input

9 4
2 4 1 2 2 19 3

Output

-1

Explanation

As no element in array has a frequency greater than or equal to k(4), the output will be -1.

Constraints

1 <= n <= 10^6

1 <= arr[i] <= 10^6

Solution of First Element to Occur K Times in java:–

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		//your code here
                Scanner sc = new Scanner(System.in);
                int n = sc.nextInt();
                int k = sc.nextInt();
                int A[] = new int[n];
                int freq[] = new int[1000001];

                for(int i=0;i<n;i++){
                        A[i] = sc.nextInt();
                }
                for(int i=0;i<n;i++){
                        freq[A[i]]++;
                        if(freq[A[i]]==k){
                                System.out.println(A[i]);
                                return;
                        }
                }
                System.out.println(-1);
	}
}