[FIXED] How to return the result if its value becomes exponentially large while formulating the no. of valid BST Permutations on the basis of number of nodes

Issue

Problem statement: You are given an Integer N. You have to determine the number of valid BST's that can be created by nodes numbered from 1 to N. Example: Input:- N = 5 arr[] = {1,2,3,4,100} Output: 1 2 5 14 25666077

My code is as follows:

CODE:
 
import java.io.*;
import java.util.*;
public class Main{
    public static int numOfTrees(int N){
        int[] t = new int[N+1];
        t[0] = 1;
        t[1] = 1;
        for(int lvl=2;lvl<=N;lvl++){
            for(int root=1;root<=lvl;root++){
                t[lvl] = t[lvl] + t[lvl-root]*t[root-1];
            }
        }
        return t[N];
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int arr[] = new int[num];
        for(int i=0;i<num;i++){
            arr[i] = sc.nextInt();
        }
        for(int i=0;i<num;i++){
            System.out.println(numOfTrees(arr[i]));
        }
    }
}

Now, when I enter 100 in arr[4] as per the sample I/P, the function returns a garbage value. I tried typecasting it into Long object type but it didn't make any difference. Please help me out folks by writing the entire program!

Solution

I rewrited your logic with BigDecimal. I hope your calculations are correct. Please point to article so I can double check the algorithm.

import java.math.BigInteger;
import java.util.*;

class Main {

    public static BigInteger numOfTrees(int N) {
        BigInteger[] t = new BigInteger[N + 1];
        for (int i = 0; i < t.length; i++) {
            t[i] = BigInteger.ZERO;
        }
        t[0] = BigInteger.ONE;
        t[1] = BigInteger.ONE;
        for (int lvl = 2; lvl <= N; lvl++) {
            for (int root = 1; root <= lvl; root++) {
                t[lvl] = t[lvl].add(
                        t[lvl - root].multiply(t[root - 1])
                );
            }
        }
        return t[N];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int arr[] = new int[num];
        for (int i = 0; i < num; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = 0; i < num; i++) {
            System.out.println(numOfTrees(arr[i]));
        }
    }
}

I entered:

5
1
2
3
4
100

=========== Output is ================

1
2
5
14
896519947090131496687170070074100632420837521538745909320

Answered By - Borislav Markov
Answer Checked By - Mildred Charles (JavaFixing Admin)