Hackerrank - Connecting Towns Solution
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.
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.
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
Total number of routes from T1 to Tn modulo 1234567
1 <= T<=1000
2< N <=100
1 <= Ni <=1000
2 3 1 3 4 2 2 2
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.
Solution in Python
#!/bin/python3 import os import sys def connectingTowns(n, routes): p = 1 for route in routes: p*=route return p%1234567 t = int(input()) for t_itr in range(t): n = int(input()) routes = list(map(int, input().rstrip().split())) result = connectingTowns(n, routes) print(result)