Ninja Fight

Easy
0/40
Average time to solve is 10m
profile
Contributed by
26 upvotes
Asked in companies
FacebookAmazonMAQ Software

Problem statement

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'.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
9
2
Sample Output 1:
2
1
Explanation for Sample Output 1:
In test case 1,

'N' = 9
Ninja 1 subtracts 3, Now 'N' = 6
Ninja 2 subtracts 1, Now 'N' = 5 
Ninja 1 subtracts 1, Now 'N' = 4
Ninja 2 subtracts 1, Now 'N' = 3
Ninja 1 subtracts 1, Now 'N' = 2
Ninja 2 subtracts and Now 'N' = 1. 

Hence Ninja 2 is the winner.


In test case 2,

'N' = 2
Ninja 1 subtracts 1, which makes 'N' = 1 and no steps for Ninja 2 to play.

Hence, Ninja 1 is the winner.
Sample Input 2:
2
1
4
Sample Output 2:
2
1
Explanation for Sample Output 2:
In test case 1,

'N' = 1 and thus Ninja 1 cannot play any turn and hence Ninja 2 is the winner.


In test case 2,

'N' = 4
Ninja 1 subtracts 1(plays optimally), Now 'N' = 3
Ninja 2 has no other choice rather than to subtract 1, Now 'N' = 2
Ninja 1 subtracts 1 and now 'N' = 1. 

Hence, Ninja 1 is the Winner.
Hint

Try to think about the cases when ‘N’ is odd or even.

Approaches (1)
Mathematics Based Approach

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 - 

  1. He can subtract any divisor of N except 1 and N.
  2. 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.

Time Complexity

O(1)

 

Since we are using the constant time to reach a solution and thus the time complexity will be O(1).

Space Complexity

O(1)

 

Since we are using constant extra memory and thus the space complexity will be O(1).

Code Solution
(100% EXP penalty)
Ninja Fight
Full screen
Console