Problem

Submissions

Hints & solutions

Discuss

Find minimum

Hard

0/120

Average time to solve is 35m

Contributed by

14 upvotes

Asked in company

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

Sample Output 2:-

1
2

Hint 1

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

Approaches (1)

Approach 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).

(100% EXP penalty)

Find minimum

Rahul

Interview problems

Find minimum

def good(mid, m, n, a):
    prev = 0


    for i in range(n):
        lf = a[i]
        rf = a[i] + mid


        # Check if prev is in the range [lf, rf] or after wrapping around modulo m
        if (prev >= lf and prev <= rf) or ((prev + m) >= lf and (prev + m) <= rf):
            continue


        # If the current element is smaller than the previous one, return True
        if lf < prev:
            return True


        prev = lf


    return False


def findMinimum(n: int, m: int, a: list) -> int:
    l, r = -1, m


    # Binary search to find the minimum number of operations
    while l < r - 1:
        mid = (l + r) // 2


        if good(mid, m, n, a):
            l = mid  # We need more operations
        else:
            r = mid  # The current mid value is sufficient


    return r

python

38 views

0 replies

0 upvotes

monish

Interview problems

python solution


def good(mid, m, n, a):
    prev = 0

    for i in range(n):
        lf = a[i]
        rf = a[i] + mid

        if (prev >= lf and prev <= rf) or ((prev + m) >= lf and (prev + m) <= rf):
            continue

        if lf < prev:
            return True

        prev = lf

    return False

def findMinimum(n: int, m: int, a: list) -> int:
    l, r = -1, m

    while l < r - 1:
        mid = (l + r) // 2

        if good(mid, m, n, a):
            l = mid
        else:
            r = mid

    return r

python

194 views

0 replies

1 upvote

Resham khadka

Interview problems

binary search solution

bool good(int mid, int m, int n, const vector<int>& a) {

int prev = 0;

for (int i = 0; i < n; i++) {

int lf = a[i];

int rf = a[i] + mid;

if ((prev >= lf && prev <= rf) || ((prev + m) >= lf && (prev + m) <= rf)) {

continue;

}

if (lf < prev) {

return true;

}

prev = lf;

}

return false;

}

int findMinimum(int n, int m, vector<int> &a) {

// int n = a.size();

int l = -1, r = m;

while (l < r - 1) {

int mid = (l + r) / 2;

if (good(mid, m, n, a)) {

l = mid;

} else {

r = mid;

}

return r;

}

437 views

0 replies

6 upvotes

Console