Game in Space
Ninja is in space with his super spaceship having unlimited fuel. Ninja initially has a health level ‘H’ and his spaceship has an armour ‘A’. He decides to play a game, where at any instant he can be only on one of the 3 planets: VENUS, MARS or SATURN. At every unit of time, he has to change his location and you can assume he can change his location instantly. Each planet has different effects on health and armour which are :

Venus: Decreases health by 4, decreases armour by 8. Mars: Increases health by 3, increases armour by 2. Saturn: Decreases health by 10, increases armour by 5.

Now the game will end if either ‘H’

Question

Game in Space

Ninja is in space with his super spaceship having unlimited fuel. Ninja initially has a health level ‘H’ and his spaceship has an armour ‘A’. He decides to play a game, where at any instant he can be only on one of the 3 planets: VENUS, MARS or SATURN. At every unit of time, he has to change his location and you can assume he can change his location instantly. Each planet has different effects on health and armour which are :

Venus: Decreases health by 4, decreases armour by 8.
Mars: Increases health by 3, increases armour by 2. 
Saturn: Decreases health by 10, increases armour by 5.

Now the game will end if either ‘H’ <= 0 or ‘A’ <= 0.

Your task is to find the maximum time Ninja can survive.

Note :

You can choose any of the 3 planets during your first move.

Input format :

The first line of input contains a single integer T, representing the number of test cases.

Then the T test cases follow.

The first line of every test case contains 2 single space-separated integers representing initial health and initial armour respectively.

Output format :

For every test case, print a single integer representing the maximum time Ninja can survive.

The output of each test case is printed in a separate line.

Note :

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= H, A <= 10^3

Where ‘T’ denotes the number of test cases,  ‘H’ is the initial health and ‘A’ is the initial armour.

Time Limit: 1sec

Accepted Answer

Recursive

The idea is simple, we will check all the possible ways of choosing planets with the help of recursion and find out which combination gives maximum time.

Along with this, we will prefer to move Mars whenever possible as it is always beneficial to make a move to Mars.

So we will make a recursive function named SOLVE which will receive 3 parameters ‘H’, ‘A’ and ‘MOVE_MARS’.
Initialize a bool variable ‘MOVE_MARS’ = 0 ,where ‘MOVE_MARS’ == 0 indicates we can move to Mars .
Base Case :
- When ‘A’ <= 0 or ‘H’ <= 0 then we will return -1 as we can’t move to any other planet now and we have already added 1 in time for this move.
Check the value of the ‘MOVE_MARS’:
- If it is equal to 0, it means we are moving to Mars.
  - Then increase ‘H’ by 3, ‘A’ by 2 and set ‘MOVE_MARS’ = 1. We then make a recursive call.
  - Return 1 + the result received in above call.
- If the ‘MOVE_MARS’ is equal to 1, it means we have to move either to Saturn or Venus.
  - Make two calls, one to Venus and other to Saturn by changing variables according to their effect and setting ‘MOVE_MARS’ = 0.
  - Return 1+ the results received in the above call.
Return the value returned by SOLVE.

Space Complexity: O(n)Explanation:

O(min(H, A) where ‘H’ is the initial health and ‘A’ is the initial armour.

The maximum depth of recursion stack space can be O(min(H, A)).

Time Complexity: O(2^n)Explanation:

O(2^min(H, A)) where ‘H’ is the initial health and ‘A’ is the initial armour.

As in each recursive call, we are making further at most 2 recursive calls till the value of ‘A’ or ‘H‘ is greater than 0.

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

So we will make a recursive function named SOLVE which will receive 3 parameters ‘H’, ‘A’ and ‘MOVE_MARS’.
We will initialize a 2-D array, say ‘MEMO[2000][2000]’ with -1. Where MEMO[i][j] equal to -1 means the current state is not explored. Otherwise, it will store the maximum time Ninja can survive with health = ’i’ and armour = ’j’.
Initialize a bool variable ‘MOVE_MARS’ = 0 ,where ‘MOVE_MARS’ == 0 indicates we can move to Mars .
Base Case :
- When ‘A’ <= 0 or ‘H’ <= 0 then we will return -1 as we can’t move to any other planet now and we have already added 1 in time for this move.
We will check the value of ‘MEMO[H][A]’ :
- If it is not equal to -1, then we can say we have already explored the result for the current state, so return ‘MEMO[H][A]’.
Check the value of the ‘MOVE_MARS’:
- If it is equal to 0, it means we are moving to Mars.
  - Then increase ‘H’ by 3, ‘A’ by 2 and set ‘MOVE_MARS’ = 1. We then make a recursive call.
  - Set ‘MEMO[H][A]’ = 1+result received in above call and return ‘MEMO[H][A]’.
- If the ‘MOVE_MARS’ is equal to 1, it means we have to move either to Saturn or Venus.
  - Make two calls, one to Venus and other to Saturn by changing variables according to their effect and setting ‘MOVE_MARS’ = 0.
  - Set ‘MEMO[H][A]’ = 1+maximum of results received in above call and return ‘MEMO[H][A]’.
Return ‘MEMO[H][A]’.

Space Complexity: O(1)Explanation:

O(1).

We are using a 2-D array of size 2000*2000 in each case as the maximum value of H+A can be 2000.

Time Complexity: OtherExplanation:

O(min(H, A)), where ‘H’ is the initial health and ‘A’ is initial armour.

We make at most 2 recursive calls till the value of ‘A’ or ‘H‘ is greater than 0 and are storing the already calculated results in ‘memo’. Hence the overall time complexity will be O(min(H, A)).

Java (SE 1.8)

/*



    Time Complexity: O(min(H, A))

    Space Complexity: O(1)



    Where H is the initial health and A is initial armour.



*/



import java.util.Arrays;



public class Solution {



    static int solve(int h, int a, int moveMars, int[][] memo) {

        // Base Case

        if (h <= 0 || a <= 0) {

            return -1;

        }



        // If we have already explored the current state

        if (memo[h][a] != -1) {

            return memo[h][a];

        }



        // Recursive calls

        if (moveMars == 0) {

            // Moving to Mars

            return memo[h][a] = 1 + solve(h + 3, a + 2, 1, memo);

        } else {

            // Moving to Venus

            int venus = 1 + solve(h - 4, a - 8, 0, memo);

            // Moving to saturn

            int saturn = 1 + solve(h - 10, a + 5, 0, memo);

            // Return the maximum of Venus and Saturn

            return memo[h][a] = Math.max(venus, saturn);

        }



    }



    public static Integer gameSpace(Integer h, Integer a) {

        int[][] memo = new int[2000][2000];



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

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

        }



        int ans = solve(h, a, 0, memo);

        return ans;

    }



}

Python (3.5)

'''



    Time Complexity: O(min(H, A))

    Space Complexity: O(1)



    Where H is the initial health and A is initial armour.



'''



def solve(h, a, moveMars, memo):

    # Base Case

    if (h <= 0 or a <= 0):

        return -1



    # If we have already explored the current state

    if (memo[h][a] != -1):

        return memo[h][a]



    # Recursive calls

    if (moveMars == 0):

        # Moving to Mars

        memo[h][a] = 1 + solve(h + 3, a + 2, 1, memo)

        return memo[h][a]

    else:

        # Moving to Venus

        venus = 1 + solve(h - 4, a - 8, 0, memo);

        # Moving to saturn

        saturn = 1 + solve(h - 10, a + 5, 0, memo);

        # Return the maximum of Venus and Saturn

        memo[h][a] = max(venus, saturn)

        return memo[h][a] 



def gameSpace(h, a):

    # Intializing the memo table

    memo = [[-1 for j in range(2000)] for i in range(2000)]

    solve(h, a, 0, memo)

    return memo[h][a]

C++ (g++ 5.4)

/*



    Time Complexity: O(min(H, A))

    Space Complexity: O(1)



    Where H is the initial health and A is initial armour.



*/



int solve(int h, int a, bool moveMars, vector>& memo) {

    // Base Case

    if (h <= 0 || a <= 0) {

        return -1;

    }



    // If we have already explored the current state

    if (memo[h][a] != -1) {

        return memo[h][a];

    }



    // Recursive calls

    if (moveMars == 0) {

        // Moving to Mars

        return memo[h][a] = 1 + solve(h + 3, a + 2, 1, memo);

    } else {

        // Moving to Venus

        int venus = 1 + solve(h - 4, a - 8, 0, memo);

        // Moving to saturn

        int saturn = 1 + solve(h - 10, a + 5, 0, memo);

        // Return the maximum of Venus and Saturn

        return memo[h][a] = max(venus, saturn);

    }



}



int gameSpace(int h, int a) {

    // Intializing the memo table

    vector> memo = vector> (2000, vector  (2000, -1));

    solve(h, a, 0, memo);

    return memo[h][a];

}

Accepted Answer

Greedy Approach

In the earlier approach, we tried to find all the possible solutions and select the one with maximum survival time, but we really do not need to find all the possible solutions. Instead, we will use some greedy approach. We can see that it is always beneficial to go to Mars so for every odd second, we will go to Mars. Now for even seconds, we are left with Venus and Saturn. So we will choose Venus if possible else we will choose Saturn, as Venus decreases health less than Saturn.

Initialize an integer variable ‘TURN’ = 0.
Run an infinite while loop:
- If ‘TURN’ is even (we can go to Mars) then do:
  - Increase ‘H’ by 3 and ‘A’ by 2.
  - Increase ‘TURN’ by 1.
- If ‘TURN’ is odd, it means we have to choose between Saturn or Venus. So, do:
  - If ‘H’ > 4 and ‘A’ > 8 (we can go to Venus):
    - Decrease ‘H’ by 4 and ‘A’ by 8.
    - Increase ‘TURN’ by 1.
  - Else if ‘H’ > 10 (we can go to Saturn):
    - Decrease ‘H’ by 10 and increase ‘A’ by 5.
    - Increase ‘TURN’ by 1.
  - If none of the above two conditions is met :
    - We can not make a move, so break the loop.
Return ‘TURN’.

Space Complexity: O(1)Explanation:

O(1).

As we are using constant extra memory.

Time Complexity: O(n)Explanation:

O(min(H, A)), where ‘H’ is the initial health and ‘A’ is the initial armour.

As we will keep on iterating till either of ‘A’ or ‘H’ is greater than 0.

Java (SE 1.8)

/*



    Time Complexity: O(min(H, A))

    Space Complexity: O(1)



    Where H is the intial health and A is the initial armour.



*/



public class Solution {

    public static Integer gameSpace(Integer h, Integer a) {

        int turn = 0;

        // Running a loop while h > 0 and a > 0

        while (h > 0 && a > 0) {

            // We can move to Mars

            if (turn % 2 == 0) {

                h += 3;

                a += 2;

            }

            // We can not move to Mars

            else {

                // If we can move to Venus, we will go to Venus

                if (h > 4 && a > 8) {

                    h -= 4;

                    a -= 8;

                }

                // If we can go to Saturn

                else if (h > 10) {

                    h -= 10;

                    a += 5;

                }

                // If we can not make a move

                else {

                    break;

                }

            }

            // Increase turn by 1

            turn++;

        }

        return turn;



    }

}

Python (3.5)

'''



    Time Complexity: O(min(H, A))

    Space Complexity: O(1)



    Where H is the intial health and A is the initial armour.



'''



def gameSpace(h, a):

    turn = 0

    # Running a loop while h > 0 and a > 0

    while (h and a):

        # We can move to Mars

        if (turn % 2 == 0):

            h += 3

            a += 2

        # We can not move to Mars

        else:

            # If we can move to Venus, we will go to Venus

            if (h > 4 and a > 8):

                h -= 4

                a -= 8

            # If we can go to Saturn

            elif (h > 10):

                h -= 10

                a += 5

            # If we can not make a move

            else:

                break

            

        # Increase turn by 1

        turn += 1



    return turn

C++ (g++ 5.4)

/*



    Time Complexity: O(min(H, A))

    Space Complexity: O(1)



    Where H is the intial health and A is the initial armour.



*/



int gameSpace(int h, int a) {

    int turn = 0;

    // Running a loop while h > 0 and a > 0

    while (h and a) {

        // We can move to Mars

        if (turn % 2 == 0) {

            h += 3;

            a += 2;

        }

        // We can not move to Mars

        else {

            // If we can move to Venus, we will go to Venus

            if (h > 4 and a > 8) {

                h -= 4;

                a -= 8;

            }

            // If we can go to Saturn

            else if (h > 10) {

                h -= 10;

                a += 5;

            }

            // If we can not make a move

            else {

                break;

            }

        }

        // Increase turn by 1

        turn++;

    }

    return turn;

}

Now the game will end if either ‘H’ <= 0 or ‘A’ <= 0.

Your task is to find the maximum time Ninja can survive.

Note :

Input format :

Output format :

Note :

Constraints :

Top TCS Assistant System Engineer interview questions & answers

Popular interview questions of Assistant System Engineer

Top HR questions asked in TCS Assistant System Engineer