Divisor Game

Easy
327.

Divisor Game

EasyMathDynamic ProgrammingBrainteaserGame TheoryAmazonAdobe

Divisor Game is an easy coding problem on dynamic programming, math and game theory, asked in Amazon and Adobe interviews.

Alice and Bob take turns with a number n on a blackboard, Alice moving first. On a turn a player picks any x with 0 < x < n and n % x == 0, then replaces n with n - x. A player who cannot move loses.

Assuming both play optimally, return true if Alice wins.

Example 1

Input
n = 2
Output
true
Explanation
Alice takes x = 1, leaving 1, and Bob has no move.

Example 2

Input
n = 3
Output
false
Explanation
Alice must take x = 1, leaving 2 for Bob, who then wins.

Example 3

Input
n = 4
Output
true

Constraints

  • 1 <= n <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {boolean}
 */
var divisorGame = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in
AI InterviewGet started

Divisor Game — Solution in Python, Java & C++

Divisor Game solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Adobe.

Divisor Game is an easy coding problem on dynamic programming, math and game theory, asked in Amazon and Adobe interviews.

Problem statement

Alice and Bob take turns with a number n on a blackboard, Alice moving first. On a turn a player picks any x with 0 < x < n and n % x == 0, then replaces n with n - x. A player who cannot move loses.

Assuming both play optimally, return true if Alice wins.

Example 1

Input: n = 2
Output: true
Explanation: Alice takes x = 1, leaving 1, and Bob has no move.

Example 2

Input: n = 3
Output: false
Explanation: Alice must take x = 1, leaving 2 for Bob, who then wins.

Example 3

Input: n = 4
Output: true

Constraints

  • 1 <= n <= 1000

Hints for Divisor Game

  1. Hint 1

    Play out the small cases with a DP over 1 … n: a position wins if some legal move leaves the opponent in a losing position.

  2. Hint 2

    The pattern that emerges is stark — look at the parity of n.

  3. Hint 3

    From an even n, taking x = 1 hands the opponent an odd number; every divisor of an odd number is odd, so they must hand back an even one.

How to solve Divisor Game

From an even n, taking x = 1 hands the opponent an odd number; every divisor of an odd number is odd, so they must hand back an even one. Even positions win, odd positions lose.

Approach

  1. Return n % 2 == 0.

Why it works

By induction: 1 is a loss (no move). Odd n has only odd proper divisors, so every move leads to an even number; even n can always subtract 1 to reach an odd number. So odd loses and even wins.

Complexity

  • Time — O(1)
  • Space — O(1)

Pitfalls

  • The O(n²) DP over positions reproduces the same parity pattern and is a fine way to discover it.

Reference solution

Python

def divisorGame(n: int) -> bool:
    return n % 2 == 0

Java

public static boolean divisorGame(int n) {
    return n % 2 == 0;
}

C++

bool divisorGame(int n) {
    return n % 2 == 0;
}

JavaScript

var divisorGame = function(n) {
    return n % 2 === 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming