Last Updated: 19 Apr, 2021
Save The World
Hard
Asked in company
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.
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
Approaches
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.
The idea is to use bit masking as the maximum integer can vary up to 20 only. There are 2 choices available with a state - pick a number or not to pick a number. So, there can be a maximum of 2^20 different states. We will store the integers that are used till now in an array, and can also find the running total with this array.
The rest of the steps are the same as the recursive approach.
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 to win 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.
- Initialize an array of size 2^'MAXIMUM_NUMBER' as there can be a maximum of 2^'MAXIMUM_NUMBER' states. In the array, if 'ARR[i]' is equal to 0, it means the state isn’t computed yet. If 'ARR[i]' is equal to 1, it means the player wins in the state and 0 otherwise.
- 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.
- Check if we have already computed the 'STATE' in the array 'DP'. If it is already computed, then we will return the computed answer.
- 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, store the answer in the array 'DP' and return true.
- If we come out of the loop, it means that there is no 'STATE' in which the opponent can win. So, store the answer in the array 'DP' return false.
The idea is to use bit masking as the maximum integer can vary up to 20 only. There are 2 choices available with a state - pick a number or not to pick a number. So, there can be a maximum of 2^20 different states. We will store the integers that are used till now in an array, and can also find the running total with this array.
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.
- Initialize an array 'DP' of size 2^'MAXIMUM_NUMBER' as there can be a maximum of 2^'MAXIMUM_NUMBER' states. In the array, if 'ARR[i]' is equal to 0, it means the state isn’t computed yet. If 'ARR[i]' is equal to 1, it means the player wins in the state and 0 otherwise.
- Iterate from i = 1 to 2^'MAXIMUM_NUMBER' - 1:
- Now, we will calculate the sum of numbers we have used from 1 to 'K' in the current state.
- If the current state doesn’t require any number, i.e. it has already crossed the 'TARGET', then ignore this state.
- Mark this state as -1 and in the iteration if we find that the current player can win, then we will mark this state accordingly.
- Iterate from ‘j’ = 1 to 'K':
- If the number is unused yet, it means we can use this number.
- Check if the desired number is greater than or equal to the current number or that the opponent lost the previous turn, it means after choosing the number the current player wins in this turn. Mark the state as the current player wins and break the loop.
- When we come out of the loop, it means we have computed for all the states. If the last index of the array 'DP' is 1, then return true as the final answer. Otherwise, return false.
Similar problems