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 = [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++