def ninjaFight(n):

# Write your code here.

if n%2==0:

return '1'

else:

return '2'

Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

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.

```
x should never be equal to the current value of 'N'.
```

Detailed explanation

```
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.
```

```
For each test case, return 1, if “Ninja 1”, wins the game, otherwise return 2 if "Ninja 2" wins the game.
```

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

```
1 <= T <= 10^5
1 <= N <= 10^9
Time limit: 1 sec
```

```
2
9
2
```

```
2
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.
```

```
2
1
4
```

```
2
1
```

```
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

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 -

- 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.

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

All tags

Sort by

Interview problems

Ninja Fight find who is winner. Python

def ninjaFight(n):

# Write your code here.

if n%2==0:

return '1'

else:

return '2'

3 views

0 replies

0 upvotes

Interview problems

O(1) Solution

If N is even, the first Ninja wins, and if N is odd, the second Ninja wins. Simple.

Logic:

If N is odd and it's my turn, then I can ONLY go to an even number(because all divisors of an odd number are odd and hence the diff of N and x would be even. So, from an odd number, I can only go to a smaller even number, no other choice.

Now, if I am at an even number, I can go to either odd or even, but I will choose x as 1 and go to N-1 which is an odd number, hence putting the opponent at a disadvantage.

This cycle of even→odd→even will keep continuing until we finally reach the last odd number, i.e 1.

28 views

0 replies

0 upvotes

Interview problems

random choice ?

I don't understand one thing in this problem .

is there need to select random input according to the user choice ?

because 9 can be divided by (1 , 3 ) but they chosen 3 .

29 views

0 replies

0 upvotes

Interview problems

What does the word optimal even mean?

public class Solution {

public static int ninjaFight(int n) {

// Write your code here.

int flag = 0;

int rev = 0;

while(n > 1) {

for(int i = n/2 - 1 ; i >= 1 ; i--) {

if(n % i == 0) {

n = n - i;

if(flag == 0) {

flag = 1;

} else {

flag = 0;

}

break;

}

}

}

}

}

48 views

0 replies

0 upvotes

Interview problems

Irrelevant Problem

This problem is irrelevant

77 views

0 replies

0 upvotes

Interview problems

Simple Game Theory

int ninjaFight(int n) {

// Write your code here.

if(n%2==0)

return 1;

else

return 2;

}

187 views

0 replies

0 upvotes

Interview problems

Dumb problem Imo

What does optimal even mean here?

This simple solution works

```
def ninjaFight(n):
if n%2 == 1:
return 2
else:
return 1
```

I thought this was the logic initially tho

```
def ninjaFight(n):
while(n>1):
x = n//2
for i in range(x,0,-1):
if n%i == 0:
n = n - i
ninja = ninja+1
break
if ninja%2 == 0:
return 2
else:
return 1
```

66 views

0 replies

0 upvotes

Interview problems

Random Function Approach

Idk what this person who post this problem came up with. Seems like a very forceful logic. According to my understanding, this question cannot have a definite answer because ninjas can subtract any number x between 1 and n from n provided n%x=0. The solution will be very random unless the values that each ninja will use are pre-determined. This is the solution that I came up with:

#include<bits/stdc++.h>

int ninjaFight(int n) {

int ninja_count=0,x;

while(n!=1)

{

x=rand()%n;

if(x>0)

{

if(n%x==0)

{

n-=x;

ninja_count++;

}

}

}

if(ninja_count%2==0)

return 2;

else

return 1;

}

105 views

1 reply

0 upvotes

Interview problems

didn't understood 'Sample outputs' ?

in sample output 1 when n=9 ninja 1 subtracted 3 because 9 is divisible by 3 but then why ninja 2 subtracted 1 and not 2 since 2 since 6 is divisible by 2.

and do we have to start taking x from 1 and stop as soon as divides n

79 views

2 replies

0 upvotes

Interview problems

Ninja Fight

```
int ninjaFight(int n) {
// Write your code here.
int ans =0;
if(n%2==0){
ans=1;
}
else{
ans=2;
}
return ans;
}
```

181 views

0 replies

0 upvotes

1

2