**Problem Statement**

Gandalf is travelling from

**Rohan**to**Rivendell**to meet Frodo but there is no direct route from**Rohan**(T1) to**Rivendell**(Tn).
But there are towns T2,T3,T4...Tn-1 such that there are N1 routes from Town T1 to T2, and in general, Ni routes from Ti to Ti+1 for i=1 to n-1 and 0 routes for any other Ti to Tj for j ≠ i+1

Find the total number of routes Gandalf can take to reach Rivendell from Rohan.

**Note**

Gandalf has to pass all the towns Ti for i=1 to n-1 in numerical order to reach Tn.

For each Ti , Ti+1 there are only Ni distinct routes Gandalf can take.

**Input Format**

The first line contains an integer T, T test-cases follow.

Each test-case has 2 lines. The first line contains an integer N (the number of towns).

The second line contains N - 1 space separated integers where the ith integer denotes the number of routes, Ni, from the town Ti to Ti+1

**Output Format**

Total number of routes from T1 to Tn modulo 1234567

**Constraints**

1 <= T<=1000

2< N <=100

1 <= Ni <=1000

**Sample Input**

```
2
3
1 3
4
2 2 2
```

**Sample Output**

```
3
8
```

**Explanation**

Case 1: 1 route from T1 to T2, 3 routes from T2 to T3, hence only 3 routes.

Case 2: There are 2 routes from each city to the next, at each city, Gandalf has 2 choices to make, hence 2 * 2 * 2 = 8.

## Source Code:

```
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) throws Exception{
/*
{
} */
int t;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String nn = br.readLine();
t = Integer.parseInt(nn);
while((t--)>0){
int num,sum,i;
BigInteger array = new BigInteger("1");
String n = br.readLine();
num = Integer.parseInt(n);
String nns[] = br.readLine().split(" ");
for(i=0;i<num-1;i++)
{
sum = Integer.parseInt(nns[i]);
array = array.multiply(new BigInteger(sum+""));
}
array = array.modPow(new BigInteger(1+""),new BigInteger(1234567+""));
System.out.println(array) ;
}
}
}
```

** The above solution is my own code and it may not be the optimal solution or optimal way to approach the problem but it passes all the testcases in Hackerrank. So if you have any optimal approaches feel free to paste the code as the comment below..... :) :) :)

please tell the logic

ReplyDelete