Divisor Game - GFG

Seriously, this question had me, spent like 15 mins thinking about this in the wrong direction. Should have thought that such types of questions are most of the time having some hidden pattern or something, CodeChef problems are generally like this only( but obviously the level of probs that I used to solve there didn't have such solutions ), I had a smidgen of feeling that maybe even odd thing, but in none of the dimensions I wud have thought that this could be the solution.

Well, in such probs we can't really say anything without properly analysing everything, cause I have seen a lot of probs on CodeChef that would sound like straight even odd kind of problems but that's just a bluff, and you would end up failing Test Cases. So I wanted to be sure without submitting my code.

The only way out of such problems is to identify in depth what's happening, so we gotta have all of these-

1) Visualise what's happening in the Game( maybe put yourself playing the game, whatever )

2) Now start with base cases and analyse all the possible cases, if this case then what? then why? then how? everything needs to be sorted with a valid reason, one mistake and you would mess up entire process.

3) Gotta see patterns in the process, like in this prob, whoever get's an even no. on Chalkboard, wins.

4)  Sleep? Yess

Gotta hit the bed, the day was fair, can't complain. See..

 Problem Statement:-

Alice and Bob take turns playing a game, with Alice starting first.
Initially, there is a number n on the chalkboard. On each player's turn, that player makes a move consisting of:

• Choosing any x with 0 < x < n  and n % x == 0.
• Replacing the number n on the chalkboard with n - x.

Also, if a player cannot make a move, they lose the game.
Return true if and only if Alice wins the game, assuming both players play optimally.

 

Example 1:

Input:
n = 2
Output: True
Explanation: Alice chooses 1, and Bob has no more moves.

 

Example 2:

Input:
n = 3
Output: False
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.

 

Your Task:
You don't need to read input or print anything. Your task is to complete the function divisorGame() which takes an integer n as a parameter and returns true if Alice wins the game.

Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ n ≤ 103

Code Implementation:- 

class Solution:

    def divisorGame(self, n):

        #Code here

        return n%2==0