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

Problem of the day

Let us say you randomly choose 'N' non-negative integers less than 'M' and put them in an array 'A'.

Find the probability that 'A' is sorted in non-decreasing order.

The answer should be found modulo 10^9 + 7. Formally, let M = 10^9 + 7. It can be shown that the answer can be expressed as an irreducible fraction p/q, where p and q are integers and q !β‘ 0 (mod M). Output the integer equal to p * (q^-1) mod M. In other words, output such an integer x that 0 <= x < M and x * q β‘ p (mod M).

```
Let 'N' = 3, 'M' = 3.
There are 27 possible final arrays.
10 of them are sorted in non-decreasing order: [ '0, 0, 0' ], [ '1, 1, 1' ], [ '2, 2, 2' ], [ '0, 1, 2' ], [ '0, 0, 1' ], [ '0, 1, 1' ], [ '0, 0, 2' ], [ '0, 2, 2' ], [ '1, 1, 2' ], [ '1, 2, 2' ].
Thus the probability needed is '(10 / 27) % (10^9 + 7) = 703703709'.
```

Detailed explanation

```
The first line of input contains a single integer 'T', which denotes the number of test cases.
Then 'T' test cases follow. For each test case:
The first and only line contains two integers, 'N' and 'M'.
```

```
For each test case, return the probability that 'A' is sorted in non-decreasing order, modulo 10^9 + 7.
```

```
You donβt need to print anything. Just implement the given function.
```

```
1 <= 'T' <= 10
2 <= 'N, M' <= 10^3
Time Limit: 1 sec
```

```
2
3 5
2 2
```

```
960000007
750000006
```

```
First test case:-
There are '5^3 = 125' possible final arrays.
Out of the arrays with 'A[ 0 ] = 0', exactly '15' are sorted in non-decreasing order.
For arrays with 'A[ 0 ] = 1', exactly '10' are sorted in non-decreasing order.
For arrays with 'A[ 0 ] = 2', exactly '6' are sorted in non-decreasing order.
For arrays with 'A[ 0 ] = 3', exactly '3' are sorted in non-decreasing order.
For arrays with 'A[ 0 ] = 4', exactly '1' is sorted in non-decreasing order.
Thus, the answer is '(35 / 125) % (10^9 + 7) = 960000007'.
Second test case:-
There are 4 possible final arrays.
3 of them are sorted in non-decreasing order: [ '0, 0' ], [ '0, 1' ], [ '1, 1' ].
Thus, the answer is '(3 / 4) % (10^9 + 7) = 750000006'.
```

```
2
25 43
60 29
```

```
43816143
973827568
```

Hint

Think of a 2 state DP solution.

Approaches

Inefficient DP

**Approach:**

- If we know two pieces of information, the current index till which we have considered and the value of the last element, we can uniquely identify all possible states.
- Thus, we can do a 2-state DP ('N' x 'M'), where 'dp[ i ][ j ]' is the probability of the prefix of 'A' till index 'i' being sorted if 'A[ i ] = j'.
- The base case is the prefix of 'A' till '0' which will be sorted with all possible values '[0, M - 1]'. Since the value is randomly chosen, the probability of each value is (1 / M), thus we can take 'dp[ 0 ][ j ] = 1 / M' for all j.
- The transition is:
- The prefix till 'i' with 'A[ i ] = j' will be sorted if the prefix till 'i - 1' is sorted and 'A[ i - 1 ] <= j'. And the probability of 'A[ i ] = j' is again (1 / M).
- That is: 'dp[ i ][ j ] += dp[ i - 1 ][ k ] / M' for all 'k <= j'.

- The final answer is the sum of 'dp[ N - 1 ][ j ]' for all j.
- Thus, we have solved the problem in O(N * M^2). Which is not fast enough.

**Algorithm:**

- Initialize two helper variables 'mod = 10^9 + 7' and 'invM = modInverse(M)'.
- Initialize a 2d array 'dp' of length 'N' x 'M'.
- Iterate using 'j' from 0 to 'M - 1' :
- Set 'dp[ 0 ][ j ]' to 'invM'.

- Iterate using 'i' from 1 to 'N - 1' :
- Iterate using 'j' from 0 to 'M - 1' :
- Iterate using 'k' from 0 to 'j' :
- Set 'dp[ i ][ j ]' to '( dp[ i ][ j ] + dp[ i - 1 ][ k ] * invM ) % mod'.

- Iterate using 'k' from 0 to 'j' :

- Iterate using 'j' from 0 to 'M - 1' :
- Initialize a variable 'ans'.
- Iterate using 'j' from 0 to 'M - 1' :
- Set 'ans' to '( ans + dp[ N - 1 ][ j ] ) % mod'.

- Return 'ans'.

Time Complexity

**O(N * M^2), where βNβ is the length of the array βAβ and βMβ is the maximum value in βAβ.**

We use three nested loops that run for a total of 'N' x 'M' x 'M' iterations. Thus, the overall time complexity is of the order O(N * M^2).

Space Complexity

**O(N * M) , where βNβ is the length of the array βAβ and βMβ is the maximum value in βAβ.**

We make a 2d array of length 'N' x 'M'. Thus, the overall space complexity is of the order O(N * M).

Code Solution

(100% EXP penalty)

Randomly Sorted