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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Divisor Game and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →