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

Problem of the day

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.

```
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

```
1 <= 'T' <= 10^5
1 <= 'N', 'M' <= 10^5
0 <= 'A[i]' < 'M'
Time Limit: 1 sec
```

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

```
2
0
```

```
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.
```

```
2
5 8
0 7 1 3 2
5 6
3 2 4 2 5
```

```
1
2
```