Description
Alice and Bob take turns playing a game, with Alice starting first. On each turn, a player chooses x from 1 to n-1 such that n % x == 0, then replaces n with n - x.
Examples
Input:
n = 2Output:
trueExplanation:
Alice picks 1, Bob loses.
Input:
n = 3Output:
falseExplanation:
Alice picks 1, leaving n=2 for Bob. Bob picks 1, leaving n=1 for Alice. Alice cannot move, so Bob wins.
Input:
n = 4Output:
trueExplanation:
Alice picks 1 (divisor of 4), leaving n=3 for Bob. Bob picks 1, leaving n=2 for Alice. Alice picks 1, leaving n=1 for Bob. Bob cannot move, so Alice wins. Even numbers always win.
Constraints
- •
1 ≤ n ≤ 1000