Divisor Game - Practice Coding Problems

Divisor Game - 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 integer x with 0 < x < n and n % x == 0
Replacing the number n on the chalkboard with n - x

If a player cannot make a move, they lose the game.

Return true if Alice wins the game, assuming both players play optimally.

Input & Output

Example 1 — Alice Loses (Odd)

$ Input: n = 3

› Output: false

💡 Note: Alice can only choose x=1, giving Bob n=2. Bob then chooses x=1, giving Alice n=1. Alice cannot move and loses.

Example 2 — Alice Wins (Even)

$ Input: n = 4

› Output: true

💡 Note: Alice chooses x=1, giving Bob n=3. Bob must choose x=1, giving Alice n=2. Alice chooses x=1, giving Bob n=1. Bob cannot move and loses.

Example 3 — Base Case

$ Input: n = 2

› Output: true

💡 Note: Alice chooses x=1 (only valid divisor), giving Bob n=1. Bob has no valid moves and loses.

Constraints

1 ≤ n ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Starting number n on chalkboard

Game Play

Players alternate choosing divisors and subtracting

Winner

Alice wins if n is even, loses if n is odd

Key Takeaway

🎯 Key Insight: Alice wins if and only if the starting number is even

Asked in

G Google 15 M Microsoft 12 F Facebook 8

The key insight is that Alice wins if and only if n is even. This is because even numbers always have the divisor 1, allowing Alice to give Bob an odd number. Best approach is mathematical pattern recognition with Time: O(1), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Pattern Recognition	O(1)	O(1)	Alice wins if and only if n is even
Recursive Simulation	O(2^n)	O(n)	Recursively try all possible moves to determine the winner
Dynamic Programming with Memoization	O(n²)	O(n)	Cache results of subproblems to avoid redundant calculations

Mathematical Pattern Recognition — Algorithm Steps

Step 1: Observe that 1 is a losing position (no valid moves)
Step 2: Notice even numbers always have odd divisors
Step 3: Even - odd = odd, so Alice can always give Bob an odd number

Visualization

Tap to expand

Step-by-Step Walkthrough

Even Numbers

Alice can always choose 1 (odd divisor)

Force Odd

Even - 1 = Odd for Bob

Bob Loses

Odd numbers only have odd divisors, leading to even numbers

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>

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

int main() {
    int n;
    scanf("%d", &n);
    bool result = solution(n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Simple modulo operation to check if n is even

✓ Linear Growth

Space Complexity

O(1)

No extra space needed, just return the result

✓ Linear Space

66.5K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Pattern Recognition — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler