Goku has ‘N’ Dragon Balls. Each Dragon Ball is unique with the ith Dragon Ball having ‘i’ stars on it. For example, the first Dragon Ball has 1 star, the second Dragon Ball has 2 stars, and so on.
Goku gave a task to Gohan to arrange the ‘N’ Dragon Balls in a binary tree-like structure. While making the binary tree, he has to make sure that these conditions must be fulfilled:
The left subtree of any particular Dragon Ball ‘D’ will always contain Dragon Balls with the number of stars less than that of the Dragon Ball ‘D’.
The right subtree of any particular Dragon Ball ‘D’ will always contain Dragon Ball's with the number of stars greater than that of the Dragon Ball ‘D’.
Can you find out how many structurally unique binary trees Gohan can make by fulfilling these conditions?
Note:The number of structurally unique binary trees can be very large, so return the number of structurally unique binary trees modulo 10^9 + 7.
The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first and the only line of each test case contains a single integer ‘N’ denoting the number of Dragon Balls.
Print the number of structurally unique binary trees satisfying the given conditions Gohan can make.
Print the output of each test case in a separate line.
You do not need to print anything; it has already been taken care of. Just implement the given function.
1 <= T <= 100
1 <= N <= 5000
Time Limit: 1 second
1
2
2
The number of possible binary trees satisfying the given conditions is two.
1 2
\ /
2 1
1
3
5
Can you compute the answer for N = n, if you know the answer for N = n - 1?
Also, think of which Dragon Ball to place at the root first and how it will affect the answer.
From the given conditions it is clear that we have to find how many structurally unique binary search trees are possible.
To find the unique BSTs, we define two functions:
A(i,N): It denotes the number of unique BSTs, with ‘i’ (1 <= ‘i’ <= N) as the root.
B(N): It denotes the number of unique BSTs for a sequence of length N (number of Dragon Balls).
Now, we construct B(N) by the sum of A(i, N) :
B(N) = A(1, N) + A(2, N) + … + A(N, N)
Notice that when we select ‘i’ as a root i.e. A(i, N), we have i - 1 nodes which can be used to form a left subtree and n - 1 nodes to form a right subtree.
A(i, N) = B(i - 1) * B(N - i)
Thus, A(i, N) can be calculated by the product of the number of unique BSTs with i - 1 nodes and the number of unique BSTs with N - i nodes. Uniqueness is guaranteed by the sizes of the left subtree and the right subtree.
Here is the algorithm :
O(N ^ N), where N denotes the number of Dragon Balls.
In the worst case at every step, we are making N recursive calls. For every ‘i’ (1 <= ‘i’ <= N) we make two recursive calls i.e one is to find the number of unique BSTs with i - 1 nodes and the other is to find the number of unique BSTs with N - i nodes. So, the maximum depth of the recursion tree can go up to N. Hence the time complexity is O(N ^ N).
O(N), where N denotes the number of Dragon Balls.
In the worst case, extra space is used by the recursion stack which can go up to a maximum depth of N. Hence the space complexity is O(N).
All tags
Sort by
Interview problems
C++ || DP || Tabulation || Easy Solution
long long m(long long a, long long b, long long mod) {
long long res = 0;
a %= mod;
while (b) {
if (b & 1) res = (res + a) % mod;
a = (2 * a) % mod;
b >>= 1;
}
return res;
}
int gokuAndDragonBalls(int n){
int i, j, M=1e9+7;
vector<int> dp(n+1, 0); dp[0]=1;
for(j=1;j<=n;j++) {
for(i=0;i<j;i++) {
dp[j] += m(dp[i], dp[j-i-1], M);
dp[j] %= M;
}
}
return dp[n];
}Interview problems
Goku and Dragon Balls || C++ Solution
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int gokuAndDragonBalls(int n) {
vector<int> dp(n + 1, 0);
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j < i; j++) {
dp[i] = (dp[i] + (1LL * dp[j] * dp[i - j - 1]) % MOD) % MOD;
}
}
return dp[n];
}
Interview problems
Easy Solution || C++ || DP
long long f(long long a, long long b, long long mod) {
long long res = 0; // Initialize result
a %= mod;
while (b) {
if (b & 1) res = (res + a) % mod;
a = (2 * a) % mod;
b >>= 1; // b = b / 2
}
return res;
}
int gokuAndDragonBalls(int n){
int i, j, M=1e9+7;
vector<int> dp(n+1, 0);
dp[0]=1;
for(j=1;j<=n;j++) {
for(i=0;i<j;i++) {
dp[j] += f(dp[i], dp[j-i-1], M);
dp[j] %= M;
}
}
return dp[n]%M;
}Interview problems
Run Time: 19ms
int gokuAndDragonBalls(int n) {
const int MOD = 1e9 + 7;
long long dp[n + 1] = {0};
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j < i; j++) {
dp[i] = (dp[i] + (dp[j] * dp[i - j - 1]) % MOD) % MOD;
}
}
return dp[n];
}
Interview problems
Simple Problem
#include<bits/stdc++.h>
int gokuAndDragonBalls(int n){
long long dp[n+1]={0},mod=1e9+7;
dp[0]=1,dp[1]=1;
for(int i=2;i<=n;i++) {
for(int j=0;j<i;j++) {
dp[i]=(dp[i]+(dp[j]*dp[i-j-1])%mod)%mod;
}
}
return dp[n]%mod;
}Interview problems
Easy C++ solution
#include<bits/stdc++.h>
int gokuAndDragonBalls(int n){
long long dp[n+1]={0},mod=1e9+7;
dp[0]=1,dp[1]=1;
for(int i=2;i<=n;i++) {
for(int j=0;j<i;j++) {
dp[i]=(dp[i]+(dp[j]*dp[i-j-1])%mod)%mod;
}
}
return dp[n]%mod;
}Interview problems
Discussion thread on Interview Problem | Goku and Dragon Balls
Hey everyone, creating this thread to discuss the interview problem - Goku and Dragon Balls.
Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Goku and Dragon Balls
