Save The World

Hard
0/120
Average time to solve is 45m
profile
Contributed by
4 upvotes
Asked in company
Apple

Problem statement

We are in the endgame now. Tony and Thanos are fighting. Before the war, Captain Marvel secretly gave Tony a superpower that she took from the other universe. They went through some days of the war but Tony’s power was enough to fight against Thanos but not to defeat him and vice versa. So, they decided to play a number game.

In the game, there are two integers - ‘maximumNumber’, and ‘target’. In each turn, one player can choose an integer and add it to ‘runningTotal’. The player who makes the ‘runningTotal’ equal to or more than the ‘target’ wins.

The rules of the game are:

1. One can use any number between 1 and ‘maximumNumber’.
2. One integer can’t be used more than once.
3. The running total = 0 initially.
4. Both players play optimally.

Thanos offered Tony to make the first move and he will choose the two integers. But the avengers are not satisfied. So, all came to a conclusion that after choosing the integers if Tony is not satisfied with the two integers, he will tell Thanos to rechoose two different integers. Tony is completely exhausted but doesn’t want to lose as it can cost us the complete universe. Help Tony to figure out if he can win or not from the two integers that Thanos chose.

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 test cases follow.

The first line contains two space-separated integers ‘maximumNumber’, and ‘target’, which denotes the maximum number that a player can choose, and the target number which whoever takes the running total more than the target wins.
Output Format: 
For each test case, print 1 if it is possible to win the game with the chosen integers. Otherwise, print 0.

Print the output of each test case in a separate line.
Note: 
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 50
1 <= maximumNumber <= 20
1 <= target <= 200

Time Limit: 1 sec
Sample Input 1:
2
5 2
5 6
Sample Output 1:
1
0
Explanation for Sample Input 1:
In the first test case, It’s Tony’s turn, he can choose any number between 1 and 5. Initially runningTotal = 0. He will choose any number between 2 and 5 and win the game. So, the output is 1.

In the second test case, Initially runningTotal = 0. It’s Tony’s turn, he has to choose any number between 1 and 5. Whichever number he will choose runningTotal will lie in the range 1 to 5. In the next turn, Thanos will choose a number between 1 and 5 which Tony didn’t choose in his turn, and win the game. So, the output is 0.
Sample Input 2:
2
10 15
10 22
Sample Output 2:
1
0
Hint

Can you figure out the base conditions for the game? Under what conditions one can win?

Approaches (3)
Recursive Approach

The idea is to use a recursive approach. We will use 'TARGET' to find what is the total sum remaining in the running total. For example, if 'TARGET' = 20 and player 1 chooses 5, then we will subtract 5 from the 'TARGET'. 

If the 'TARGET' becomes less than or equal to 0, it means that the current player loses and the player who played the last turn has won already. 

As there are different states and players are playing optimally, we need to traverse from 1 to the 'MAXIMUM_NUMBER' and check for the number which we haven’t used till now. If any of the further recursive calls return false it means the opponent can’t win, it means the current player wins.

 

But there is a base condition: 

 

What if the sum of all the integers from 1 to 'MAXIMUM_NUMBER' is not sufficient to add up to 'TARGET'?

Base Condition 1: In this case, both the players can’t win. So, the answer will be false. We will check the given condition before calling the recursive function.

 

There are some more base conditions:

 

  • Base Condition 2: If the 'TARGET' is less than or equal to 1, it means Tony(the player whose turn is first) wins as he can choose any integer.
  • Base Condition 3: If the sum of integers from 1 to 'MAXIMUM_NUMBER' is equal to the 'TARGET', it means if the 'MAXIMUM_NUMBER' is even, then the player who plays at then even turns wins and if the 'MAXIMUM_NUMBER' is odd, then the player who plays in the odd turns wins. the player who plays at the odd turns wins. For example if 'MAXIMUM_NUMBER' = 2 and 'TARGET' = 3, then Tony chooses 1, Thanos chooses 2 and Thanos wins.
  • If 'MAXIMUM_NUMBER'= 3 and 'TARGET' = 6, then Tony chooses 1, Thanos choses 2, Tony chooses 3 and Tony wins.
  • Tony begins, and then Thanos, etc. The player who will play the last turn will win the game and that will be the player who plays in the odd turns.

 

The steps are as follows:

 

  • Calculate the sum of integers from 1 to 'MAXIMUM_NUMBER'.
  • Base Condition 1: If the sum is less than the 'TARGET', return false as no one can win the game.
  • Base Condition 2: If the 'TARGET' is less than or equal to 1, return true as Tony can choose any number to win.
  • Base Condition 3: If the sum of integers from 1 to 'MAXIMUM_NUMBER' is equal to the 'TARGET', it means if the 'MAXIMUM_NUMBER' is even, then the player who plays at then even turns wins and if the 'MAXIMUM_NUMBER' is odd, then the player who plays in the odd turns wins. the player who plays at the odd turns wins.
  • Define a recursive function currentStateAnswer which takes 4 arguments and returns if player 1 wins or not. The arguments are 'MAXIMUM_NUMBER', 'TARGET', 'DP', 'STATE' which denotes the maximum number that a player can choose, the 'TARGET' number which whoever takes the running total more than the 'TARGET' wins, the array to store the results of the stages, and the current stage for which we are playing the current turn respectively.
    • If the current 'TARGET' is less than or equal to 0, return false as the player who played the last turn won.
    • Iterate over all the numbers remaining for choosing, and check if there exists a state in which the opponent can’t win, it means the current player wins. So, return true.
  • If we come out of the loop, it means that there is no state in which the opponent can win. So, we will return false.
Time Complexity

O(M^(M+1)), where M is the maximum number given.

 

As we are having recursive calls of maximum depth M and for each call there are at most M calls. Hence, the overall time complexity is O(M^(M+1)).

Space Complexity

O(M^(M+1)), where M is the maximum number given.

 

As we are having recursive calls of maximum depth M and for each call there are at most M calls. Hence, the overall space complexity is O(M^(M+1)).

Code Solution
(100% EXP penalty)
Save The World
Full screen
Console