Maximum Occuring Integer


You are given an array A of N integers.You have created K copies of the given array and concatenated them with initial array

Now you are given Q queries and for each query , you are provided with two numbers L and R

Task:

Determine the maximum occurring integer from index L to R(both inclusive) in the final array. If there is more than one maximum occurring integer,then print the largest integer.

Example

Assumptions

A=[1,2,3]

K=3

Approach

After concatenation the final array would look like [1,2,3,1,2,3,1,2,3].

For L=1,R=9 answer =3 as it occurs 3 times and is larger than 1,2 which are also occurring 3 times

For L=1,R=5 answer =2 as it occurs 2 times and is larger than 1

Input format:

The first line contains 3 integers N,K and Q

The next line contains N space separated values representing the elements of array A

The next Q lines contains two space separated integers L and R

Output format

For each query print the required answer in a new line

 

Code(python 3)

 

def finding(lst,l,r):

    mp = dict()

    op=[]

    lst=lst[int(l):int(r)]

    for i in range(len(lst)):

        if lst[i] in mp.keys():

            mp[lst[i]] += 1

        else:

            mp[lst[i]] = 1

    for i in range(len(lst)):

        if mp[lst[i]] == max(mp.values()):

            op.append(lst[i])

    return max(op)

n,k,q=map(int,input().split())

lst = []

lst = list(map(int,input().strip().split()))[:n]

for i in range(k):

    lst=lst+lst

for i in range(q):

    l,r=input().split()

    print(finding(lst,l,r))


Image