Proble asked in sabre campus hiring test

#1

Queries and operations

You are given N coins of different value val, that are arranged in a row. You are given Q queries of the following format

.0 X Y:Compute the sum of all the special coins in interval X, N.
• 1 X Y: Compute the multiplication of all the special coins in interval (X, N).

For each query, the Xth position contains a special coin. Here, a coin is considered a special coin if the distance of its index from the index of any other special coin is evenly divisible by Y. For example, if coin at i = 2 is special and the value of Y is 3, then coin at i=5 ,8 , 11 are also considered as special coins.

Note: Since the answers can be large, print the answer modulus 10^9 + 7.

Input format

• The first line contains T denoting the number of test cases,

• The first line of each test case contains N denoting the number of coins.

• The second line of each test case contains N space-separated integers denoting the value of each coin

• The third line of each test case contains Q denoting the number of queries

• Next Q lines of each test case contain three space-separated integers that contain 0 or 1, X, and Y

Output format

Print the answer for each query in a separate line.
Constraints

1<=T<=10

I<N,Q<= 5 x 10^4

1<=X,Y<=N

1<=val<=10^9

Note: It is advisable to use fast Vo for this problem.

Sample input 1

1 5

23547

4

813

122

015

131

30

<-30

1.0

+20

Copy

Sample output 1

6

12

2

140

#2

Hint: Square Root Decomposition

#3

sir please help nhi ho rha h this question is asked in sabre corporation… They will ask same in interview…I have asked friends from other colleges they told they will ask same questions as of written test

#4

Should I tell the complete solution then, or you want me to provide hints?

#5

please sircomplete solution

#6

sir please reply… i have tried this many times

#7

Case 1
for cases when y > 1000, that is, difference given is greater than 1000 in query

Now, note that, the brute force will take O(n x ( n / y)) which in worst case is approx. =
(5 x 10^4) x (5 x 10^4) / 1000 = 2.5 x 10^6.

So brute force will work for this case.

Case 2
when y < 1000, that is, difference given in query is less than 1000

Now, bruteforce won’t work, but we can do precalculation in this part.
for every difference y = d, calculate the sum/product of arrays at a distance of d.

For example, for d:
presum arrays will be like

sum[0] = arr[0], arr[0] + arr[d], arr[0] + arr[d] + arr[2d], arr[0] + arr[d] + arr[2d] + arr[3d], ....
sum[1] = arr[1], arr[1] + arr[1 + d], arr[1] + arr[1 + d] + arr[1 + 2d], arr[1] + arr[1 + d] + arr[1 + 2d] + arr[1 + 3d], ....
sum[2] = arr[2], arr[2] + arr[2 + d], arr[2] + arr[2 + d] + arr[2 + 2d], arr[2] + arr[2 + d] + arr[2 + 2d] + arr[2 + 3d], ....
sum[3] = arr[3], arr[3] + arr[3 + d], arr[3] + arr[3 + d] + arr[3 + 2d], arr[3] + arr[3 + d] + arr[3 + 2d] + arr[3 + 3d], ....
sum[4] = arr[4], arr[4] + arr[4 + d], arr[4] + arr[4 + d] + arr[4 + 2d], arr[4] + arr[4 + d] + arr[4 + 2d] + arr[4 + 3d], ....
.
.
sum[d - 1] = ...

Now, to answer a query of let’s say x = 5, y = 2, we can simply return the sum from one of the presums array.

so for every d, we will have n corresponding values, hence in total 1000 * n values are stored
which in worst case = 5 x 10^6, and can be easily stored.

#8

@yashmalik.official
@Jun18APP0112
please share the code