##### Short Problem Definition:

Gandalf is travelling from **Rohan** to **Rivendell** to meet Frodo but there is no direct route from **Rohan** (T_{1}) to **Rivendell** (T_{n}).

But there are towns T_{2},T_{3},T_{4}…T_{n-1} such that there are N_{1} routes from Town T_{1} to T_{2}, 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.

##### Link

##### Complexity:

time complexity is O(N)

space complexity is O(1)

##### Execution:

This is a simple combinatorics problem. Even though python ints don’t overflow easily, I added the MOD anyways. The code in GoLang is also available.

##### Solution:

MOD = 1234567 def main(): t = input() for _ in xrange(t): n = input() arr = map(int, raw_input().split()) routes = 1 for value in arr: routes = ( routes * value ) % MOD print routes if __name__ == '__main__': main()

func connectingTowns(n int32, routes []int32) int32 { result := int32(1) for _, value := range routes { result = (result*value) % 1234567 } return result }

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.