Search

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

1. generate all subarrays of A.

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

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

4. 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 =  ```

Example Output

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

Example Explanation

```Explanation 1:
subarrays of A    maximum element
                1
[1, 2]              2
[1, 2, 4]            4
                2
[2, 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 = 1 => [ {1} ]
freq = 2 => [ {1,2}, {2} ]
freq = 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 = 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 = 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] = 1, freq = 1, store = {1,1}
prod[A] = 2, freq = 2, store = {2,2}
prod[A] = 8, freq = 3, store = {8,3}```

Code:

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

```Now,
store = {8,3}
store = {2,2}
store = {1,1}```

Code:

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

```store = {8,3}
store = {2,5}    // 3 + 2 = 5
store = {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)`

Code in C++