# Kth Occurrence Queries DSA Problem Solution

Kth Occurrence Queries DSA Problem Solution

In this post, we are going to solve Kth Occurrence Queries DSA Problem from JP Morgan Chase, Online Assessments conducted on 29th October,2022. Let’s have a look at the problem statement first and then try to solve the problem.

## Kth Occurrence Queries DSA Problem Statement

There is an array of integers, arr, and an integer value

$X$$X$. For each element in another array of integers, query_values, return the 1-based index in arr of the query_values[i] occurrence of

$X$$X$. If

$X$$X$ does not occur query_values[i] times, return -1 for that query.

Example

arr = [1, 2, 20, 8, 8, 1, 2, 5, 8, 0]

$X=8$$X =8$

query_values = [100, 4, 2]

There is no 100th or 4th instance of

$X=8$$X = 8$ in arr. The 2nd occurrence is at index 5. Return [-1,-1, 5].

Input

The first line contains

$n$$n$ the number of elements in the array. The second line contains

$n$$n$ elements separated by space denoting the array arr. The third line contains int

$X$$X$, the integer to search for. The fourth line contains an integer

$q$$q$ denoting the length of the query array. The fifth line contains the

$q$$q$ integers separated by space denoting query values that is the occurrence of

$X$$X$ to find the index of.

$\left(1\le n,q\le 2\cdot {10}^{5}\right)$$(1 \le n,q \le 2 \cdot 10^5)$

$\left(0\le ar{r}_{i},X,\le {10}^{9}\right)$$(0 \le arr_{i},X,\le 10^9)$

$\left(1\le quer{y}_{i}\le {10}^{9}\right).$$(1 \le query_{i} \le 10^9).$

Output

int[q]: the index in arr or -1 for each query

Example
Input
10
1 2 4 5 8 8 9 0 9 8
8
3
1000000 2 3

Output
-1
6
10


## Problem Solution in C++

#include <bits/stdc++.h>
using namespace std;

int main() {

int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
int x;
cin>>x;
vector<int> pos;
for(int i=0;i<n;i++){
if(a[i]==x){
pos.push_back(i+1);
}
}
int q;
cin>>q;
vector<int> ans;
while(q--){
int id;
cin>>id;
if(id>pos.size()){
ans.push_back(-1);
}
else{
ans.push_back(pos[id-1]);
}
}
for(auto v:ans)cout<<v<<' ';
cout<<'\n';

return 0;

}

## Problem Solution in Java

import java.util.*;
import java.io.*;
public class Main {
static final Random random=new Random();
static long mod=1000000007L;
static HashMap<String,Integer>map=new HashMap<>();

public static void main(String args[]) throws IOException {
int n=in.nextInt();
Map<Integer,Integer> m=new HashMap<>();
int x=in.nextInt();
int c=1;
for(int i=0;i<n;i++){
if(arr[i]==x){
m.put(c,i+1);
c++;
}
}
int p=in.nextInt();
for(int i=0;i<p;i++){
int t1=in.nextInt();
if(!m.containsKey(t1))System.out.print(-1+" ");
else System.out.print(m.get(t1)+" ");
}
}

static int max(int a, int b)
{
if(a<b)
return b;
return a;
}
static void ruffleSort(int[] a) {
int n=a.length;
for (int i=0; i<n; i++) {
int oi=random.nextInt(n), temp=a[oi];
a[oi]=a[i]; a[i]=temp;
}
Arrays.sort(a);
}

static < E > void print(E res)
{
System.out.println(res);
}

static int gcd(int a,int b)
{
if(b==0)
{
return a;
}
return gcd(b,a%b);
}

static int lcm(int a, int b)
{
return (a / gcd(a, b)) * b;
}

static int abs(int a)
{
if(a<0)
return -1*a;
return a;
}

{
StringTokenizer st;

{
}

String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
return Integer.parseInt(next());
}

long nextLong()
{
return Long.parseLong(next());
}

double nextDouble()
{
return Double.parseDouble(next());
}
String nextLine()
{
String str = "";
try
{
}
catch (IOException e)
{
e.printStackTrace();
}
return str;
}

}