Find minimum

Hard
0/120
Average time to solve is 35m
profile
Contributed by
19 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
Hint

Look out for the range of values you can get for each element by performing any finite number of operations.

Approaches (1)
Binary search

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'.
Time Complexity

O(NlogN), where 'n' is the size of array 'a'.

since we are just initializing a variable, it takes O(NlogN) time. Hence, The overall time complexity is of the order O(N*logN)

Space Complexity

O(1).

since we are only using some constant variables, which will take O(1) space. so, the space complexity is O(1).

Code Solution
(100% EXP penalty)
Find minimum
Full screen
Console