Count Ways To Travel Triangular Pyramid

Moderate
0/80
Average time to solve is 20m
4 upvotes
Asked in companies
MicrosoftMakeMyTripOYO

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.

Example

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
Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1 :

2
1
2

Sample Output 1 :

0
3

Explanation of the Sample Input 1:

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.

Sample Input 2 :

2
3
4

Sample Output 2 :

6
21
Hint

 Can you think about a recursion solution?

Approaches (3)
Brute Force

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.
  • 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.
Time Complexity

O(3 ^ N), where ‘N’ is the number of steps.

 

As during each call to function we are making further 3 calls thus making time complexity as O(3 ^ N).

Space Complexity

O(N), where ‘N’ is the number of steps.

 

This is the space-complexity used by the recursion stack.

Code Solution
(100% EXP penalty)
Count Ways To Travel Triangular Pyramid
Full screen
Console