| Submit | All submissions | Best solutions | Back to list |
VECTAR6 - Number of Binary Trees |
Changu has to deal with a very simple problem. He has to find the number of binary trees of height n where for each node the left subtree is at least as high as the right subtree.
NOTE: The height of the binary tree here is in terms of the nodes, i.e, number of nodes in the path from the root to the deepest leaf node. Hence, the height of a tree with only root node is 1.
Input
The first line contains T, the number of test cases. The following T lines contain a number N.
Output
For each N output the number of binary trees of height N where for each node the left subtree is at least as high as the right subtree. As the answer can be large, you have to print answer modulus 1000000007
Example
Input: 2 1 2 Output: 1 2
Constraints
T = 100000
1 <= N <= 10000000
| Added by: | Piyush Kumar |
| Date: | 2016-07-03 |
| Time limit: | 1.5s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 GOSU JS-MONKEY |
hide comments
|
2023-12-16 03:30:40
Useful testcases: 7 1 2 3 4 5 6 7 output without modulo division: 1 2 8 96 10368 108615168 11798392572168192 |
|
|
2016-07-07 22:55:54
@piyush can u please tell me where i have gone wrong with my last submission...I believe i'm doing it correctly Last edit: 2016-07-08 05:58:47 |
|
|
2016-07-04 12:28:16
@psetter-is o(1) solution possible?? Re: The intended solution is to answer each query in O(1). Good luck :) Last edit: 2016-07-04 12:36:46 |
|
|
2016-07-04 11:42:31 Piyush Kumar
The problem statement has been updated to make things more clear ! |
|
|
2016-07-04 09:51:56
@Vipul: I initially took the height as the number of edges from the root to the deepest leaf but in this problem, it is the number of nodes on the path from root to the deepest leaf. :) |
|
|
2016-07-04 07:59:40 Vipul Srivastava
@pranav what do you mean by the statement that height is in terms of nodes?? |
|
|
2016-07-04 02:32:06
How is the answer 1 for n=1? There are two binary trees that satisfy the condition for n=1. With two nodes, 1-2 and with three nodes, 1-2, 1-3. EDIT: Height is in terms of nodes. Also, please mention that we have to find the answer modulo 10**9+7. Re: Updated, thanks :) Last edit: 2016-07-04 11:00:42 |
RSS