LOVEBIRDS - She was in Love with BST
Devo! She has broken up with him again!
And after a series of break ups and patch ups , she is done with him!
Being a geek to keep herself distracted, she picks up her favourite topic of dynamic programming where she comes across this idiot problem which says
Given a integer N , you have to tell the sum of number of structurally unique Binary search trees built on different permutations of the set{x , x such that x belongs to [1,N] and x is an integer}.
A Binary Search tree is said to be built on a permutation iff the in-order traversal of that BST is same as the permutation.
A permutation is said to be distinct from another if there exists a position i such that the i th element of both the permutations is different.
Now, her inability to solve the problem is quite stressful to her! Help her in Solving the problem!
NOTE: She observes that this number can be very large so output this number Modulo 1908 .
Moreover she tells you that there in-order traversal of a Binary search tree is Unique.
For Binary Search Tree Read https://en.wikipedia.org/wiki/Binary_search_tree
Input
The first line of the input consists of T , the number of test cases.
The following T lines consists of a single integer N
(N can be at max 1000 , T can be at max 1000)
Output
You have to Output T lines each consisting of the answer to the problem Modulo 1908
Example
Input: 2 1 2 Output: 1 2
hide comments
surajxd:
2020-08-30 10:28:03
catalan number..
|
|
kushrike:
2020-05-22 23:54:55
No need of catalan numbers. Just visualise the BST when node 'i' is the root. Rest is simple P & C. |
|
raipavitra:
2020-02-16 17:43:33
simple p and c with recurrence.
|
|
aman_sachin200:
2018-06-15 22:59:26
Awesome One!!!No need to know Catalan Numbers....form a recurrence and then its pretty easy to solve..loved solving it!!!! :P |
|
mahilewets:
2017-09-13 22:18:03
I have forgot formula for Catalan numbers
|
|
heisenberg0820:
2017-06-23 11:33:19
@aman_9899 Pro _/\_
|
|
aman_9899:
2017-06-20 21:00:59
hint : catalan numbers...!!!
|
|
steady_bunny:
2017-06-09 07:54:38
May be Catalan numbers will be useful have a look on them!!! |
|
maverick_10:
2015-12-10 00:00:27
Did this in 0.02sec feeling very great!!!
|
|
Aman Kumar:
2015-08-19 11:18:27
how is the answer for 2 is 2 ?
|
Added by: | psych_cod3r |
Date: | 2015-08-17 |
Time limit: | 1s |
Source limit: | 1000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 MAWK BC NCSHARP COFFEE DART FORTH GOSU JS-MONKEY JULIA KTLN OCT PROLOG PYPY3 R RACKET SQLITE SWIFT UNLAMBDA |
Resource: | Intuition |