Leetcode 1025. Divisor Game

Problem statement

https://leetcode.com/problems/divisor-game/

Solution

One way to solve is to use dp. However this problem can solved easier: if number is even, we can always make it odd, subtracting 1. If number is odd, all divisors are odd and it must be even on the next steps. So, odd values are winning positions and even values are loosing positions.

Complexity

It is O(1) for time and space.

Code

class Solution:
    def divisorGame(self, n):
        return not n%2