# Simple Queries InterviewBit Solution

Problem: Simple Queries

Problem Description:

You are given an array A having N integers.

You have to perform the following steps in a given order.

generate all subarrays of A.

take the maximum element from each subarray of A and insert it into a new array G.

replace every element of G with the product of their divisors mod 1e9 + 7.

sort G in descending order

You now need to perform Q queries In each query, you are given an integer K, where you have to find the Kth element in G. Note: Your solution will run on multiple test cases so do clear global variables after using them.

Problem Constraints

```
1 <= N <= 1e5
1 <= A[i] <= 1e5
1 <= Q <= 1e5
1 <= k <= (N * (N + 1))/2
```

Input Format

```
The first argument given is an Array A, having N integers.
The second argument given is an Array B, where B[i] is the ith query.
```

Output Format

`Return an Array X, where X[i] will have the answer for the ith query.`

Example Input

```
Input 1:
A = [1, 2, 4] B = [1, 2, 3, 4, 5, 6]
```

```
Input 2:
A = [1, 3] B = [1]
```

Example Output

```
Output 1:
[8, 8, 8, 2, 2, 1]
```

```
Output 2:
[3]
```

Example Explanation

```
Explanation 1:
subarrays of A maximum element
[1] 1
[1, 2] 2
[1, 2, 4] 4
[2] 2
[2, 4] 4
[4] 4
original G = [1, 2, 4, 2, 4, 4]
after changing every element of G with product of their divisors
G = [1, 2, 8, 2, 8, 8]
after sorting G in descending order G = [8, 8, 8, 2, 2, 1]
```

Explanation 2:

`Just perform given query. `

## Approach

Let's solve it step by step.

1. For each element find, in how many subarrays it is the maximum element.

```
For example, A = [1,2,4]
freq[0] = 1 => [ {1} ]
freq[1] = 2 => [ {1,2}, {2} ]
freq[2] = 3 => [ {1,2,4}, {2,4}, {4} ]
```

To compute frequency we can multiply, the number of consecutive elements at the left and right side.

```
For example:
A = [0, 5, 1, 2, 3, 4, 3, 5]
For the element A[5] = 4,
number of consecutive elements at the left side = 4 [1,2,3,4]
number of consecutive elements at the right side = 2 [4,3]
So frequency, freq[5] = 4*2 = 8.
Similarly, you can check it for others.
```

We can use stack to compute it in O(n).

Code:

2. Store the frequency element with the product of its divisors in pair.

```
For example, A = [1,2,4]
prod[A[0]] = 1, freq[0] = 1, store[0] = {1,1}
prod[A[1]] = 2, freq[1] = 2, store[1] = {2,2}
prod[A[2]] = 8, freq[2] = 3, store[2] = {8,3}
```

Code:

3. Sort store array in decreasing order with respect to the first element.

```
Now,
store[0] = {8,3}
store[1] = {2,2}
store[2] = {1,1}
```

Code:

4. Store cumulative sum of frequency, in store array.

```
store[0] = {8,3}
store[1] = {2,5} // 3 + 2 = 5
store[2] = {1,6} // 5 + 1 = 6
```

- This shows that from 1 to 3rd position answer is 8, from 4th to 5th position answer is 2 and for 6th position, the answer is 1.

Code:

5. We can do binary search on the store array's first element, to find our desired result.

Code:

## Time & Space Complexity

`Time Complexity: O(NlogN)`

- For finding divisors, it is similar to the Sieve of Eratosthenes, and for each query, we are doing binary search.

`Space Complexity: O(N)`

## Solution:

Code in C++

Hey, can you explain the frequency part, why you're multiplying number of consecutive elements, I was unable to understand. Thanks