Last Updated: 3 Dec, 2021
Win or Lose
Easy
Asked in company
You and your friends are playing a turn-based game. You will make the first move. Initially, you have an integer ‘N’. On each player’s turn, that player makes a move consisting of two steps.
1) Choose an integer ‘i’ such that 0 < ‘i’ < ‘N’ and ‘N’ is divisible by ‘i’.
2) Update number ‘N’ to ‘N - i’.
If a player cannot make a move, they lose the game.
You are given the initial number ‘N’. You have to print “YES” if you win the game; otherwise, print “NO”.
For example:
If the number ‘N’ = 6 and you select ‘i’ to be 2, then the new number ‘N’ will be 6 - 2 = 4.
Input Format-
First-line contains ‘T’, denoting the number of Test cases.
For each Test case:
The first line contains an integer, ‘N’, denoting the starting number.
Output Format-
For each test case, you have to print “YES” if you win the game; otherwise, print “NO”.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints -
1 <= ‘T’ <= 5000
1 <= ‘N’ <= 10^9
Time Limit: 1 sec
Approaches
Approach: For each number, we will store whether the number is the winning number or not (i.e. If a person present at number ‘i’ wins, then the ‘ith’ number is considered as the winning number). For ‘i’ to be a winning number, there must be a number ‘j’ that follows the condition 0 < ‘j’ < ‘i’, ‘i’ is divisible by ‘j’, and the number ‘j’ is not a winning number.
Algorithm:
- Create an array ‘dp’ of length ‘N + 1’ and initialize its values to 0.
- Iterate using a for loop from i = ‘2’ to ‘N’.
- Iterate using a for loop from j = ‘1’ to ‘Sqrt(i)’.
- If ‘i’ is divisible by ‘j’.
- If dp[i - j] is 0.
- Update dp[i] to 1.
- Break.
- If j != 1 and dp[i - (i / j)] is 0.
- Update dp[i] to 1.
- Break.
- If dp[i - j] is 0.
- If ‘i’ is divisible by ‘j’.
- Iterate using a for loop from j = ‘1’ to ‘Sqrt(i)’.
- If dp[N] is 1.
- Print “YES”.
- Else.
- Print “NO”.
Approach: You will win if the number ‘N’ is even, else you lose. Let's suppose you win for all the even integers in the range (0, 2 * k] if you start at that number. Then for the number '2 * k + 2', you can subtract '1'. Now the new number is '2 * k + 1', which is an odd number. So, your friend can only choose an odd integer to subtract, and after subtracting, the new number is an even number in the range (0, 2 * k]. So you win the game. We can see that you will win if the number is even else; you lose the game.
Algorithm:
- If the number is even.
- Print “YES”.
- Else.
- Print “NO”.