Count Ways to travel Triangular Pyramid — Asked in Microsoft and Amazon Interview

Problem Statement :

Bob has been given a triangular pyramid with its vertices marked as ‘O’, ‘X’, ‘Y’ and ‘Z’ and provided with another integer ’N’. In a single step, Bob can go to any adjacent vertices. Bob will always start from ‘O’ and has to return to ‘O’ after making exactly ’N’ steps.

Your task is to find out the number of ways he can take to complete his journey.

As the answer can be very large, return the answer by taking modulo with 1000000007.

Sample Input:

1

Sample Output:

0

Sample Input:

2

Sample Output:

3

Explanation of given Test Cases :

For the first test case:
There is no way we can start from ‘O’ and end up at ‘O’ because we will be either on ‘X’, ’Y’ or ‘Z’. Hence 0 ways.    

For the second test case:
The possible ways are from ‘O’ we go to ‘X’ then back to ‘O’. Similarly for ‘Y’ and ‘Z’. Hence 3 ways.

Approach :

One observation we can make is that the number of ways to reach the position ‘X’ ={‘O’,’X’,’Y’,’Z’} in the current step is equal to the sum of the number of ways Bob is not at position ‘X’ in the previous steps.

1. We will initialize a 2-D array say DP [4][N+1] with 0, where N is the number of steps. DP[i][j] will store the number of ways to reach ‘i’ with ’N’ equal to ‘j’.

2. Here column 0 is for position ‘O’, 1 for ‘X’,2 for ‘Y’ and 3 for ‘Z’.

3. Set DP[0][0] is qaul to 1.

4. Run a loop for 1 <= i <= N and do:

• Intialise an integer variable ‘TEMP’ = 0.
• Run a loop for 0 <= j <= 3 and do:
• DP[j][i] = DP[(j+1)%4][i-1] + DP[(j+2)%4][i-1] + DP[(j+3)%4][i-1] .

5. Return DP[0][N].

Time Complexity: O(N)
Space Complexity: O(N)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.