Last Updated: 4 Mar, 2021
Count Ways To Travel Triangular Pyramid
Moderate
Asked in companies
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.
Note :
As the answer can be very large, return the answer by taking modulo with 1000000007.
For example :
If ‘N’=1
So in 1 step we can reach either to ‘X’ , ‘Y’ or ‘Z’ and can not travel back to ‘O’.
Thus there are 0 ways.
If ‘N’ =2
So there are total three ways :
(i) O->X->O
(ii) O->Y->O
(iii) O->Z->O
If ‘N’ = 3
So there are total 6 ways :
(i) O->X->Y->O
(ii) O->X->Z->O
(iii) O->Y->X->O
(iv) O->Y->Z->O
(v) O->Z->X->O
(vi) O->Z->Y->O
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains a single integer ‘N’ denoting the number of steps.
Output format :
For each test case, print a single integer denoting the number of ways.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 10000
Where ‘T’ is the total number of test cases, and 'N’ is the number of steps you can make.
Time Limit: 1 sec.
Approaches
The idea is very simple, as standing at any point we will always have three choices to move. So we will make a recursive function and call it for all three choices and decrease ‘N’ by 1 each time. So when ‘N’ will reach 0 then we will check the current position, if it is ‘O’ then we can say we have found a way.
Complete Algorithm :
- We will make a helper recursive function named ‘SOLVE’ which will receive 2 parameters ‘N’, ‘POS’.
- Here ‘POS’ will be initialized with ‘O’.
- Base Case:
- If ‘N’ is equal to zero:
- If ‘POS’ is equal to ‘O’ then do:
- Return 1.
- Otherwise do:
- Return 0.
- If ‘POS’ is equal to ‘O’ then do:
- If ‘N’ is equal to zero:
- Recursive Calls:
- Decrease ‘N’ by 1.
- Intialise an integer variable ‘ANS’ = 0.
- If ‘POS’ is equal to ‘O’ then do :
- ANS += Make a recursive call with ‘POS’ as ‘X’.
- ANS += Make a recursive call with ‘POS’ as ‘Y’.
- ANS += Make a recursive call with ‘POS’ as ‘Z’.
- Similarly, we can make calls for different values of ‘POS’.
- Return ‘ANS’.
- Return the value returned by the ‘SOLVE’ function.
Our last approach was very simple and easy, but its time complexity was of exponential order. We can improve our solution by taking care of the overlapping subproblems. Thus, we will eliminate the need for solving the same subproblems again and again by storing them in a lookup table. This approach is known as Memoization.
We will initialize a 2-D array say MEMO [4][N+1] with -1, where N is the number of steps. Where MEMO[i][j] equals to -1 means the current state is not explored. Otherwise, MEMO[i][j] will store the number of ways to reach ‘i’ with ‘N’ equal to ‘j’.
So there will be two modification to the earlier approach :
- In Base Case, first of all, we will check the value of MEMO if it is not equal to -1, then simply return the value stored in the MEMO.
- In Recursive Calls, before returning the ‘ANS’ we will store the value in MEMO.
As our earlier approach recursion with memoization surely avoided some subproblems but we can still improve time complexity using a bottom-up 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.
- 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’.
- Here column 0 is for position ‘O’, 1 for ‘X’,2 for ‘Y’ and 3 for ‘Z’.
- Set DP[0][0] is qaul to 1.
- 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] .
- Return DP[0][N].