Find minimum

Hard

0/120

Average time to solve is 35m

Contributed by

13 upvotes

Asked in company

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