Find minimum

Hard

0/120

Average time to solve is 35m

Contributed by

6 upvotes

Problem statement

Alice is given the number 'M'. She is also given an array 'A' of 'N' integers where 0 <= A[i] <= 'M' - 1. She can perform any number of operations on the array. In one operation, Alice can choose any set of indices(maybe none) of the array 'A' and make 'A[i]' = ('A[i]+1') % 'M', where 'i' is the chosen index and 0 <= 'i' < 'N'. You are asked to find the minimum number of such operations required to make the array non-decreasing.

Return a number 'C' denoting the minimum number of such operations required to make the array non-decreasing.

Note: Assume 0-based indexing.

For example:

Let 'N' = 5, 'M' = 7, and 'A' = [0, 6, 1, 3, 2]. In the first operation, Alice will choose elements at indices 1 and 4, 'A[1]' = 6 and 'A[4]' = 2. The array becomes [0, 0, 1, 3, 3]. As it is non-decreasing after a single operation. Hence, the answer is 1.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:-

The first line contains an integer 'T', which denotes the number of test cases.

For every test case:-

The first line contains two integers, 'N', and 'M' denoting the size of the array 'A' and the above-mentioned variable respectively.

The next line contains 'N' space-separated integers denoting the elements of the array 'A'.

Output Format:-

For each test case, Return a number 'C' denoting the minimum number of such operations required to make the array non-decreasing.

Note:-

You don’t need to print anything. Just implement the given function.

Constraints:-

1 <= 'T' <= 10^5
1 <= 'N', 'M' <= 10^5
0 <= 'A[i]' < 'M'

Time Limit: 1 sec

Sample Input 1:-

2
6 4
1 3 3 1 3 2
5 3
0 0 0 1 2

Sample Output 1:-

2
0

Explanation of sample input 1:-

First test case:- 
In the first operation, Alice will choose indices 0, 3, and 5. Then the array 'A' will become [2, 3, 3, 2, 3, 3]. In the next operation, Alice will choose indices 0, 3 and the array becomes [3, 3, 3, 3, 3, 3]. Now, the array is non-decreasing. Hence, the answer is 2.

Second test case:-
As the array is already non-decreasing, the answer is 0.

Sample Input 2:-

Sample Output 2:-

1
2

Console