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
hide comments
|
smso:
2023-12-16 03:30:40
Useful testcases:
|
|
akash25:
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 |
|
azam_9:
2016-07-04 12:28:16
@psetter-is o(1) solution possible??
|
|
Piyush Kumar:
2016-07-04 11:42:31
The problem statement has been updated to make things more clear ! |
|
pranav_arora:
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. :) |
|
Vipul Srivastava:
2016-07-04 07:59:40
@pranav what do you mean by the statement that height is in terms of nodes?? |
|
|
pranav_arora:
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.
|
| 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 |
RSS