Short Problem Definition:

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.

Link

Connecting Towns

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.