Skip to main content

1025. Divisor Game

easy

Alice and Bob alternate turns; on each turn the current player picks a proper divisor of n and replaces n with n minus that divisor. Whoever cannot move loses. Determine if Alice wins — the answer collapses to a parity check via DP.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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, then 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.

Constraints

  • 1 <= n <= 1000

Examples

Example 1

Input
n = 2
Output
true

Explanation: Alice chooses 1, leaving Bob with n = 1 which has no proper divisor; Bob loses.

Example 2

Input
n = 3
Output
false

Explanation: Alice must choose 1, leaving Bob with n = 2; Bob then wins as in example 1.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Define dp[i] = true if the player to move at value i wins with optimal play.

Hint 2

Base case: dp[1] = false (no move available).

Hint 3

Transition: dp[i] = true iff some proper divisor x of i has dp[i - x] = false (move to a losing position for the opponent).

Solution approach

Reveal approach

Define the subproblem dp[i] = the current player wins when the chalkboard shows i. The recurrence relation is dp[i] = true iff there exists a proper divisor x of i (1 <= x < i, i % x == 0) such that dp[i - x] = false; the current player wins by moving to any position where the next player loses. Base case dp[1] = false. Compute dp[2..n] iteratively: for each i, scan x from 1 to i-1 (or up to sqrt(i) by symmetry) and check the recurrence. Return dp[n]. Running this small DP reveals dp[i] = (i is even) — the player on an even n always wins by playing x = 1, flipping the parity for the opponent and preserving it for themselves. So the one-line answer is return n % 2 == 0, but the DP framing is the part interviewers actually probe.

Complexity

Time
O(n * sqrt(n))
Space
O(n)

Related patterns

  • dynamic-programming
  • memoization-recursion
  • game-theory

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

More Dynamic Programming practice problems

See all Dynamic Programming problems →