Last Updated: 16 Dec, 2020
Ninja Fight
Easy
Asked in companies
Two Ninjas, “Ninja 1” and “Ninja 2”, are here to fight and they want to prove themselves stronger than the other, and to prove so they decided to play a game and whosoever will be the winner of the game will be stronger than the other.
The Game is, given an integer 'N' at the start, the Ninja in his turn has to select a positive integer x such that 'N' is divisible by x ('N' % x = 0) and subtract x from 'N'. The game stops when 'N' becomes 1, now if both the Ninjas alternate their turns starting from “Ninja 1”, your task is to determine the winner if both the Ninjas play optimally.
The player who makes the last move is the winner i.e. The player who is unable to make the move is the loser.
Note:
x should never be equal to the current value of 'N'.
Input Format:
The first line of the input contains an integer 'T' denoting the number of test cases.
The first and the only line of each test case contains an integer 'N' as described in the problem statement.
Output Format:
For each test case, return 1, if “Ninja 1”, wins the game, otherwise return 2 if "Ninja 2" wins the game.
Note:
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10^5
1 <= N <= 10^9
Time limit: 1 sec
Approaches
It can be clearly seen that if ‘N’ =1, Second Player wins. Similarly if ‘N’ = 2 then the player who starts wins.
Now we move further and see that if ‘N' is odd (greater than 1) or even(greater than 2).
Case 1 - ‘N’ is Even:
The possible two moves the first player can make are -
- He can subtract any divisor of N except 1 and N.
- He can subtract 1(1 is a divisor of every natural number).
We can clearly see that whenever he subtracts 1(example N=4, then Ninja 1 plays optimally and subtracts 1 to make ‘N’ = 3), the other player gets an odd number(in our example ‘N’ = 3). Also now we know that the divisor of every odd number is odd. Therefore the other Ninja has to subtract an odd number, either 1 or any other odd number. In both cases, we’re subtracting an odd number from another odd number which will give us an even number(in our example we have to subtract 1, now ‘N’ = 2 and Ninja 1 finally wins). Hence the player who’ll start first will always prefer to decrease ‘N’ by 1 at each move to get an even value of ‘N’ for his next move until ‘N’ finally becomes 2 and he wins.
Case 2 - ‘N’ Is Odd:
In this case, the player who starts first has to strictly subtract 1 from ‘N’ to get an even value of ‘N’ for the second player. Now using the same logic as in Case 1, we can say the second player wins if he plays optimally, which simply requires decreasing the value of ‘N’ at every move. The second player can also reach his victory by choosing a bigger value of an odd integer rather than 1.
The losing player can delay the outcome by decreasing the value of ‘N’ by 1 at each of his moves.