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

Problem of the day

You are given two integers ‘M’ and ‘N’. Your task is to find the number of a unique beautiful array of length ‘M’.

The array of length ‘M’ is said to be beautiful if -

```
The array consists of elements from 1 to ‘N’.
The array contains at least one ‘N’ length strictly increasing subsequence.
```

Note:

```
A subsequence of an array is an ordered subset of the array's elements having the same sequential ordering as the original array. For example, the subsequences of the array [1, 2, 3] are [1], [2], [3], [1, 2], [1, 3], [2, 3] and [1, 2, 3] where [2, 1], [3,2, 1] are not subsequence of array [1, 2, 3]
The longest increasing subsequence of an array of numbers is the longest possible subsequence that can be created from its elements such that all elements are in strictly increasing order.
```

For example:

```
For M = 3 and N = 2
array : [ 1, 1, 2 ] [ 1, 2, 1 ] [ 1, 2, 2 ] [ 2, 1, 2 ] are beautiful.
array: [ 1, 1, 1 ] [ 2, 1, 1 ] [ 2, 2, 1 ] [ 2, 2, 2 ] are not beautiful.
```

Detailed explanation

```
1 <= Q <= 500
1 <= N <= M <= 5 * 10 ^ 3
Time Limit: 1 sec.
```

```
2
3 2
4 3
```

```
4
9
```

```
In the query case, M = 3 and N = 2
array : [ 1, 1, 2 ] [ 1, 2, 1 ] [ 1, 2, 2 ] [ 2, 1, 2 ] are beautiful. So the answer is 4.
In the second query,.M = 4, N = 3
array [1 1 2 3] [1 2 1 3] [1 2 2 3] [1 2 3 1] [1 2 3 2] [1 2 3 3] [1 3 2 3] [2 1 2 3] [3 1 2 3] are beautiful. So the answer is 9.
```

```
1
4 4
```

```
1
```

```
In the first query, only [1 2 3 4] is a beautiful array.
```