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
11 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 )
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