Last Updated: 8 Nov, 2022

Find minimum

Hard

Asked in company

Solve now

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.

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

Solve now

Approaches

01 Approach

Approach:-

Let's check that the answer to the problem is ≤ 'x'. Then, for each element, you have some interval (interval on the "circle" of remainders modulo m) of values that it can be equal to. For example, 'm' = 6 and array 'A' = [1, 2, 4] and for 'x' = 3 the range for 'A[0]' is (1,4), for 'A[1]' is (2,5), and for 'A[2]' is (4,1).

So we need to check, if we can pick in each interval some point, to make all these values non-decreasing.

We can do it greedily! Each time, let's take the smallest element from the interval, that is at least the previously chosen value.

If the array 'A' can be made non-decreasing using 'x' number of operations, then it can also be done in 'x+1' operations. As we can choose none of the indices of the array for the 'x+1'th operation. So, make a binary search on 'x' for the minimum number of operations.

Algorithm:-

Make a bool function 'good' with parameters 'mid', 'm', 'n', and the array 'a'
- Initialize the variable 'prev' with 0.
- Run a for loop with variable 'i' and range 0 to 'n-1'.
  - Initialise a variable 'lf' with 'a[i]' and 'rf' with 'a[i]+m';
  - If the value of 'prev' or 'prev+m' is between 'lf' and 'rf'.
    - Continue.
  - If 'lf' is less than 'prev'
    - Return true.
  - Else
    - 'prev'= 'lf'.
- Return false.
Initialize a variable 'l' with -1 and 'r' with 'm'.
Run a while loop for 'l' < 'r-1'
- Initialize a variable 'mid' with '(l+r)/2'.
- If 'good(mid, m, n, a)'
  - 'l' = 'mid'
- Else
  - 'r' = 'mid'
Return 'r'.

Solve now