Count Ways To Travel Triangular Pyramid
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

Question

Count Ways To Travel Triangular Pyramid

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

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.

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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

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

Time Complexity: O(3^n)Explanation:

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).

Accepted Answer

Recursion + Memoization

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.

Space Complexity: O(n)Explanation:

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

As we will are using a 2-D array/list ‘MEMO’ of size 4 * N.

Time Complexity: O(n)Explanation:

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

In the worst case, after making N calls all the states will be explored and after that, we can use the result from ‘MEMO’.

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the number of steps.  

*/



#define mod 1000000007



int solve(int n, char pos, vector>& memo) 

{

    // Base Case.

    if (n == 0) 

    {

        if (pos == 'O') 

        {

            return 1;

            

        }

        return 0;

    }



    // Recursive Calls.

    n = n - 1;

    int ans = 0;

    if (pos == 'O') 

    {

        if (memo[0][n + 1] != -1) 

        {

            // As we have decrease n by 1.

            return memo[0][n + 1];



        }

        ans = (ans + solve(n, 'A', memo)) % mod;

        ans = (ans + solve(n, 'B', memo)) % mod;

        ans = (ans + solve(n, 'C', memo)) % mod;

        return memo[0][n + 1] = ans;



    } 

    else if (pos == 'A') 

    {

        if (memo[1][n + 1] != -1) 

        {

            // As we have decrease n by 1.

            return memo[1][n + 1];



        }

        ans = (ans + solve(n, 'O', memo)) % mod;

        ans = (ans + solve(n, 'B', memo)) % mod;

        ans = (ans + solve(n, 'C', memo)) % mod;

        return memo[1][n + 1] = ans;



    }

    else if (pos == 'B') {

        if (memo[2][n + 1] != -1) 

        {

            // As we have decrease n by 1.

            return memo[2][n + 1];



        }

        ans = (ans + solve(n, 'A', memo)) % mod;

        ans = (ans + solve(n, 'O', memo)) % mod;

        ans = (ans + solve(n, 'C', memo)) % mod;

        return memo[2][n + 1] = ans;



    }

    else 

    {

        if (memo[3][n + 1] != -1) 

        {

            // As we have decrease n by 1.

            return memo[3][n + 1];



        }

        ans = (ans + solve(n, 'A', memo)) % mod;

        ans = (ans + solve(n, 'B', memo)) % mod;

        ans = (ans + solve(n, 'O', memo)) % mod;

        return memo[3][n + 1] = ans;



    }



}



int countWays(int n) 

{

    char pos = 'O';

    int ans = 0;

    vector> memo = vector> (4, vector (n + 1, -1));

    return solve(n, pos, memo);



}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the number of steps.

'''



mod = 1000000007



def solve(n, pos, memo):



    # Base Case.

    if (n == 0):

        if (pos == 'O'):

            return 1

        

        return 0



    # Recursive Calls.

    n = n - 1

    ans = 0

    if (pos == 'O'):

        if (memo[0][n + 1] != -1):



            # As we have decrease n by 1.

            return memo[0][n + 1]



        ans = (ans + solve(n, 'A', memo)) % mod

        ans = (ans + solve(n, 'B', memo)) % mod

        ans = (ans + solve(n, 'C', memo)) % mod

        memo[0][n + 1] = ans

        return memo[0][n + 1]



    elif (pos == 'A'):

        if (memo[1][n + 1] != -1):



            # As we have decrease n by 1.

            return memo[1][n + 1]



        ans = (ans + solve(n, 'O', memo)) % mod

        ans = (ans + solve(n, 'B', memo)) % mod

        ans = (ans + solve(n, 'C', memo)) % mod

        memo[1][n + 1] = ans

        return memo[1][n + 1]



    elif (pos == 'B'):

        if (memo[2][n + 1] != -1):



            # As we have decrease n by 1.

            return memo[2][n + 1]

        

        ans = (ans + solve(n, 'A', memo)) % mod

        ans = (ans + solve(n, 'O', memo)) % mod

        ans = (ans + solve(n, 'C', memo)) % mod

        memo[2][n + 1] = ans

        return memo[2][n + 1]



    else:

        if (memo[3][n + 1] != -1):

            

            # As we have decrease n by 1.

            return memo[3][n + 1]



        ans = (ans + solve(n, 'A', memo)) % mod

        ans = (ans + solve(n, 'B', memo)) % mod

        ans = (ans + solve(n, 'O', memo)) % mod

        memo[3][n + 1] = ans

        return memo[3][n + 1]



def countWays(n):

    pos = 'O'

    ans = 0

    memo = [[-1 for j in range(n + 1)] for i in range(4)]

    return solve(n, pos, memo)

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the number of steps.  

*/



import java.util.Arrays;



public class Solution {

    

    static int mod = 1000000007;

    

    public static int solve(int n, char pos, int memo[][]) {



        // Base Case.

        if (n == 0) {

            if (pos == 'O') {

                return 1;



            }

            return 0;

        }

        // Recursive Calls.

        n = n - 1;

        int ans = 0;

        if (pos == 'O') {

            if (memo[0][n + 1] != -1) {



                // As we have decrease n by 1.

                return memo[0][n + 1];

            }

            ans = (ans + solve(n, 'A', memo)) % mod;

            ans = (ans + solve(n, 'B', memo)) % mod;

            ans = (ans + solve(n, 'C', memo)) % mod;

            return memo[0][n + 1] = ans;

            

        } else if (pos == 'A') {

            if (memo[1][n + 1] != -1) {



                // As we have decrease n by 1.

                return memo[1][n + 1];

            }

            ans = (ans + solve(n, 'O', memo)) % mod;

            ans = (ans + solve(n, 'B', memo)) % mod;

            ans = (ans + solve(n, 'C', memo)) % mod;

            return memo[1][n + 1] = ans;

        } else if (pos == 'B') {

            if (memo[2][n + 1] != -1) {



                // As we have decrease n by 1.

                return memo[2][n + 1];

            }

            ans = (ans + solve(n, 'A', memo)) % mod;

            ans = (ans + solve(n, 'O', memo)) % mod;

            ans = (ans + solve(n, 'C', memo)) % mod;

            return memo[2][n + 1] = ans;



        } else {

            if (memo[3][n + 1] != -1) {

                

                // As we have decrease n by 1.

                return memo[3][n + 1];

            }

            ans = (ans + solve(n, 'A', memo)) % mod;

            ans = (ans + solve(n, 'B', memo)) % mod;

            ans = (ans + solve(n, 'O', memo)) % mod;

            return memo[3][n + 1] = ans;

        }

    }

    

    public static int countWays(int n) {

        char pos = 'O';

        int ans = 0;

        int memo[][] = new int[4][n+1];

        for(int i = 0; i < 4; i++){

            Arrays.fill(memo[i],-1);

        }

        return solve(n, pos, memo);

    }

}

Accepted Answer

Bottom-Up DP

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].

Space Complexity: O(n)Explanation:

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

As we will are using a 2 - D array of size 4 * N.

Time Complexity: O(n)Explanation:

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

As we are running a loop from 1 to ‘N’.

Python (3.5)

'''

    Time Complexity: O(N) 

    Space Complexity: O(N)



    Where N is the number of steps.   

'''



mod = 1000000007



def countWays(n):

    dp = [[0 for j in range(n + 1)] for i in range(4)]

    dp[0][0] = 1

    for i in range(n + 1):

        for j in range(4):

            dp[j][i] = (dp[j][i] + (dp[(j + 1) % 4][i - 1])) % mod

            dp[j][i] = (dp[j][i] + (dp[(j + 2) % 4][i - 1])) % mod

            dp[j][i] = (dp[j][i] + (dp[(j + 3) % 4][i - 1])) % mod

            

    return dp[0][n]

C++ (g++ 5.4)

/*

    Time Complexity: O(N) 

    Space Complexity: O(N)



    Where N is the number of steps. 

*/



#define mod 1000000007



int countWays(int n) 

{

    vector> dp = (vector> (4, vector  (n + 1, 0)));

    dp[0][0] = 1;

    for (int i = 1; i <= n; i++) 

    {

        for (int j = 0; j <= 3; j++) 

        {

            dp[j][i] = (dp[j][i] + (dp[(j + 1) % 4][i - 1])) % mod;

            dp[j][i] = (dp[j][i] + (dp[(j + 2) % 4][i - 1])) % mod;

            dp[j][i] = (dp[j][i] + (dp[(j + 3) % 4][i - 1])) % mod;

        }

    }

    

    return dp[0][n];

}

Java (SE 1.8)

/*

    Time Complexity: O(N) 

    Space Complexity: O(N)



    Where N is the number of steps.   

*/



public class Solution {

    

    static int mod = 1000000007;

   

    public static int countWays(int n) { 

        int dp[][] = new int[4][n+1];

        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {

            for (int j = 0; j <= 3; j++) {

                dp[j][i] = (dp[j][i] + (dp[(j + 1) % 4][i - 1])) % mod;

                dp[j][i] = (dp[j][i] + (dp[(j + 2) % 4][i - 1])) % mod;

                dp[j][i] = (dp[j][i] + (dp[(j + 3) % 4][i - 1])) % mod;

            }

        }

        return dp[0][n];

    }

}

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

Note :

For example :

Input format :

Output format :

Note:

Constraints:

Top Oyo Rooms Software Developer interview questions & answers

Popular interview questions of Software Developer