# 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++