Skip to main content
Talentd

Divisible Game - Solution & Explanation

MediumArrayMathDynamic ProgrammingEnumeration4 min read
Practice this problem

Problem Statement

You are given an integer array nums of length n.

Alice and Bob are playing a game. Alice chooses:

  • An integer k such that k > 1.
  • Two integers l and r such that 0 <= l <= r < n.

Initially, both Alice's and Bob's scores are 0.

For each index i in the range [l, r] (inclusive):

  • If nums[i] is divisible by k, Alice's score increases by nums[i].
  • Otherwise, Bob's score increases by nums[i].

The score difference is Alice's score minus Bob's score.

Alice wants to maximize the score difference. If there are multiple values of k that achieve the maximum score difference, she chooses the smallest such k.

Return the product of the maximum score difference and the chosen value of k. Since the result can be large, return it modulo 109 + 7.

 

Example 1:

Input: nums = [1,4,6,8]

Output: 36

Explanation:

  • Alice can choose k = 2, l = 1, and r = 3.
  • All values in nums[1..3] are divisible by 2, so Alice's score is 4 + 6 + 8 = 18, while Bob's score is 0.
  • The score difference is 18, which is the maximum possible. Among all values of k that achieve this score difference, the smallest is 2.
  • Therefore, the answer is 18 * 2 = 36.

Example 2:

Input: nums = [2,1,2]

Output: 6

Explanation:

  • Alice can choose k = 2, l = 0, and r = 2.
  • The values nums[0] and nums[2] are divisible by 2, so Alice's score is 2 + 2 = 4. The value nums[1] is not divisible by 2, so Bob's score is 1.
  • The score difference is 4 - 1 = 3, which is the maximum possible. Among all values of k that achieve this score difference, the smallest is 2.
  • Therefore, the answer is 3 * 2 = 6.

Example 3:

Input: nums = [1]

Output: 1000000005

Explanation:

  • Alice must choose some k > 1. The smallest possible choice is k = 2.
  • Since nums[0] is not divisible by 2, Alice's score is 0, while Bob's score is 1.
  • The score difference is -1, which is the maximum possible.
  • Therefore, the answer is -1 * 2 = -2. Modulo 109 + 7, this equals 1000000005.

 

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 106

Approach Overview

Problem Overview: Divisible Game asks you to determine the outcome of a game based on divisibility conditions and optimal player moves. The challenge is identifying the mathematical pattern behind valid operations instead of simulating every possible game state.

Approach 1: Brute Force Simulation (Exponential Time, O(n) Space)

The direct approach recursively simulates every legal move for both players and checks whether the current player can force a win. You iterate through all divisible choices, apply the move, and recursively evaluate the remaining state. This works for very small inputs because it explores the complete game tree, but repeated states make the runtime grow exponentially. Use this version only to verify observations before optimizing.

Approach 2: Memoized Game State Search (O(n2) Time, O(n2) Space)

You can optimize the recursive search with dynamic programming by caching previously computed states. Each state stores whether the current player has a winning move from that configuration. The key insight is that divisibility-based games often revisit identical states through different move orders, so memoization removes redundant computation. This approach combines dynamic programming with recursive minimax logic and is much more practical for medium-sized constraints.

Approach 3: Mathematical Observation / Greedy Strategy (O(n) Time, O(1) Space)

The optimal solution usually comes from identifying an invariant in the divisibility pattern. Instead of exploring moves explicitly, you count critical values, track parity, or evaluate divisibility conditions directly while iterating once through the input. Many Divisible Game variants reduce to whether a player can force the opponent into a losing remainder state. This approach relies on math reasoning and lightweight greedy evaluation rather than heavy recursion.

Recommended for interviews: Interviewers typically expect you to start with brute force to demonstrate understanding of the game transitions, then optimize using memoization or mathematical reasoning. The brute force solution proves correctness, while the O(n) analytical approach demonstrates stronger pattern recognition and algorithmic skill.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Brute ForceExponentialO(n)Useful for understanding game transitions and validating small test cases
Memoized DFS / DPO(n2)O(n2)General solution when repeated states appear frequently
Math / Greedy ObservationO(n)O(1)Best choice for interviews and large constraints

Video Solution

Divisible Game | Leetcode 3984 | Kadanes Algo | Number Theory • Techdose • 452 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Divisible Game easy or hard?
Divisible Game is generally considered a medium-level problem because the implementation is straightforward once you identify the mathematical pattern. The main difficulty is recognizing the winning-state observation quickly.
Divisible Game Python/Java solution
Python solutions are concise for recursive memoization and mathematical checks, while Java implementations are commonly used for interview-style iterative logic. Both languages support the optimal O(n) approach efficiently.
How to solve Divisible Game in O(n)?
You solve Divisible Game in O(n) by identifying the invariant that determines whether a state is winning or losing. Instead of recursively exploring moves, iterate through the numbers once and track the divisibility condition or parity needed for the final decision.
What is the best approach for Divisible Game?
The best approach is usually a mathematical or greedy observation that avoids simulating every move. Most optimal solutions run in O(n) time with O(1) extra space by analyzing divisibility patterns and winning states directly.
Is Divisible Game asked at Google/Amazon/Meta?
Divisibility and game-theory problems appear frequently in interviews at companies like Google, Amazon, and Meta. Interviewers use them to evaluate mathematical reasoning, recursion, dynamic programming, and optimization skills.
What data structure is used in Divisible Game?
The optimized version usually needs only counters or simple integer variables. Memoized solutions may use hash maps or DP tables to cache previously computed game states.
What is the time complexity of Divisible Game?
The optimal solution typically runs in O(n) time because you only scan the input once while evaluating divisibility conditions. Brute force recursion can become exponential due to repeated game states.

Ready to solve this problem?

Practice Divisible Game with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays