10609. First element occurring k times in array

 

Given an array of n integers. Find the first element that occurs k number of times. If no element occurs k times, print -1.

 

Input. The first line contains numbers n and k (n, k ≤ 105). Second line contains n integers, each no more than 109 by absolute value.

 

Output. Print the first element that occurs k times. If no element occurs k times, print -1.

 

Sample input 1

Sample output 1

7 2

1 7 4 3 4 8 7

7

 

 

Sample input 2

Sample output 2

6 1

4 1 6 1 6 4

-1

 

 

SOLUTION

data structures map

 

Algorithm analysis

For each number x from the sequence, count in the map data structure the number of times m[x] it occurs in the sequence. Then find the first element of the sequence for which m[x] = k (that occurs k times).

 

Algorithm realization

Declare the data structures.

 

map<int, int> m;

vector<int> v;

 

The main part of the program. Read the input sequence into array v. For each number x count in m[x] the number of times it occurs in the sequence.

 

scanf("%d %d", &n, &k);

for (i = 0; i < n; i++)

{

  scanf("%d", &x);

  v.push_back(x);

  m[x]++;

}

 

Iterate over the elements of the sequence. As soon as v[i] is found, that occurs k times, print it and exit the program.

 

for (i = 0; i < n; i++)

  if (m[v[i]] == k)

  {

    printf("%d\n", v[i]);

    return 0;

  }

 

The required value is not found. Print -1.

 

printf("-1\n");

 

Java realization

 

import java.util.*;

 

public class Main

{

  static Map<Integer, Integer> m = new HashMap<Integer, Integer>();

  static ArrayList<Integer> a = new ArrayList<Integer>();

 

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    int k = con.nextInt();

 

    for (int i = 0; i < n; i++)

    {

      int x = con.nextInt();

      a.add(x);

      int val = (m.containsKey(x)) ? m.get(x) : 0;

      m.put(x, val + 1);

    }

   

    for (int i = 0; i < n; i++)

      if (m.get(a.get(i)) == k)

      {

        System.out.println(a.get(i));

        con.close();

        return;

      }

   

    System.out.println(-1);

    con.close();

  }

}