Win or Lose

Easy
0/40
Average time to solve is 20m
profile
Contributed by
16 upvotes
Asked in company
Goldman Sachs

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input-1
2
2
3
Sample Output-1
YES
NO
Explanation for Sample Input 1:
For test case 1:
    You can choose only ‘1’; the new number becomes 2 - 1 = 1.
    Your friend can’t make any move. Hence you win the game.
For test case 2:
    You can choose only ‘1’; the new number becomes 3 - 1 = 2.
    Your friend can choose only ‘1’; the new number becomes 2 - 1 = 1.
You can’t make any move. Hence you lose the game.
Sample Input -2
2
13
16
Sample Output -2
NO
YES
Hint

How does the win or loss depend on the previous number?

Approaches (2)
DP

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[N] is 1.
    • Print “YES”.
  • Else.
    • Print “NO”.
Time Complexity

O(N * sqrt(N)), where N is the given number.

 

We are running a ‘for’ loop inside a ‘for’ loop. Hence the overall complexity is O(N * sqrt(N)).

Space Complexity

O(N), where N is the given number.

 

We are creating an array of length ‘N’. Hence the overall complexity is O(N).

Code Solution
(100% EXP penalty)
Win or Lose
Full screen
Console