Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Find minimum

Hard
0/120
Average time to solve is 35m
profile
Contributed by
13 upvotes
Asked in company
RedBus

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:-
2
5 8
0 7 1 3 2
5 6
3 2 4 2 5
Sample Output 2:-
1
2
Full screen
Console