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

Beautiful Array

Hard
0/120
Average time to solve is 50m
profile
Contributed by
9 upvotes
Asked in companies
GoogleDirectiFlock

Problem statement

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 ( Input/output format, Notes, Images )
Constraints:
1 <= Q <= 500
1 <= N <= M <= 5 * 10 ^ 3

Time Limit: 1 sec.
Sample Input 1:
2
3 2
4 3
Sample Output 1:
4
9
Explanation of Sample Input 1:
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.
Sample Input 2:
1
4 4
Sample Output 2:
1
Explanation of Sample Output 2:
In the first query, only [1 2 3 4] is a beautiful array.
Full screen
Console