Hackerrank - Connecting Towns Solution

Gandalf is travelling from Rohan to Rivendell to meet Frodo but there is no direct route from Rohan (T₁) to Rivendell (T_n).

But there are towns T₂,T₃,T₄...T_n-1 such that there are N₁ routes from Town T₁ to T₂, and in general, N_i routes from T_i to T_i+1 for i=1 to n-1 and 0 routes for any other T_i to T_j 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 T_i for i=1 to n-1 in numerical order to reach T_n.
For each T_i , T_i+1 there are only N_i 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 i^th integer denotes the number of routes, N_i, from the town T_i to T_i+1

Output Format
Total number of routes from T₁ to T_n modulo 1234567
http://en.wikipedia.org/wiki/Modular_arithmetic

Constraints
1 <= T<=1000
2< N <=100
1 <= N_i <=1000

Sample Input

2
3
1 3
4
2 2 2

Sample Output

3
8

Explanation
Case 1: 1 route from T₁ to T₂, 3 routes from T₂ to T₃, 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)