1

Boxes and chocolates

Difficulty: NINJA
Avg. time to solve
55 min
Success Rate
45%

Problem Statement
Suggest Edit

Kevin has three children and he wants to buy chocolates for them. The shopkeeper has ‘N’ boxes of chocolates (numbered from 1 to ‘N’). Each box has some amount of chocolates. If Kevin selects the “i-th” box for buying the chocolates then he must have to buy all the chocolates present in that box. Kevin wants to distribute an equal amount of chocolates among his children.

This problem is divided into 3 subproblems. You must have to solve all three subproblems.

FIRST:

You have to find the maximum number of ways in which Kevin can buy the chocolates if he is allowed to choose boxes in random order.

SECOND:

You have to find the maximum number of ways in which Kevin can buy the chocolates if he is only allowed to choose the consecutive boxes.

THIRD:

There are ‘Q’ queries given to you and each query can be of two types:

0 I V
1 L R

The first type has 0 as a first character that represents this is an update query in which you have to update the number of chocolates in the “Ith” box to ‘V’.

The second type has 1 as a first character that represents this is a range query in which you have to find the maximum number of ways in which Kevin can buy the chocolates in the range [L, R] if he is allowed to choose boxes in any order.

Note:

1. There is no need to maximize the number of chocolates bought by Kevin. 
2. Consider 1 based indexing for queries. There must be a single query of type 1. 
3. You have to take the modulo with 10^9 + 7 as the result can be very large.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’ which denotes the number of chocolate boxes in the shop.

The second line of each test case contains ‘N’ space-separated integers which denote the number of chocolates in a particular box.

The third line of each test case will contain a single integer ‘Q’ which denotes the number of queries.

The next ‘Q’ lines contain three integers “0 I V” or “1 L R” in which ‘I’ represents the index whose value will have to be updated to ‘V’. ‘L’ and ‘R’ represent the inclusive range for which the result has been asked.
Output Format:
For each test case, print the result of all three subproblems in order such that:

In the first line, the result of subproblem 1 (FIRST) is printed.

In the second line, the result of subproblem 2 (SECOND) is printed.

In the third line, the result of each range query of type 1 is printed and each integer must be separated by a single space.

Output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 100
1 <= ARR[ i ] <= 10^5
1 <= Q <= 100
1 <= I, L, and R <= N
1 <= V <= 10^5

Where "ARR[i]” is the number of chocolates in the “i-th” box, ‘Q’ is the number of queries, and ‘I’, ‘V’, ‘L’, and ‘R’ are described in the Input format.

Time limit: 1 sec
Sample Input 1:
1
4
2 3 5 8
2
0 1 3
1 1 3
Sample Output 1
3
2
3
Explanation of sample input 1:
In the first test case, the number of ways in which Kevin can buy the chocolates if he chooses boxes in any order is 3 ([2, 5, 8], [3], [2, 3, 5, 8]), if he chooses only consecutive boxes then answer is 2 ([2, 3, 5, 8] and [3]) and after updating the array answer for the range query is 3 ([3], [3], [3,3]).
Sample Input 2:
2
1
12
4
0 1 2
1 1 1
0 1 3
1 1 1
3
3 1 3
2
0 2 3
1 1 3
Sample Output 2:
1
1
0 1
3
2
7
Explanation for sample input 2:
In the second test case, Results for each subproblem are as follows:
FIRST :- [3], [3, 3], and [3].
SECOND :- [3], and [3]
THIRD :- [3], [3, 3], [3, 3], [3, 3, 3], [3], [3, 3], and [3].
Reset Code
Full screen
copy-code
Console