Divisible Game solution and explanation
4 more videos on this problem
Divisible Game | Leetcode 3984 | Kadanes Algo | Number TheoryTechdose · 38:20 · 452 views
Leetcode 3984 | Divisible Game | Leetcode weekly contest 509 | Number TheoryCodeWithMeGuys · 26:27 · 328 views
Divisible Game | LeetCode 3984 | Weekly Contest 509 | Optimal ApproachDesiCoding · 16:42 · 153 views
3984. Divisible Game (Leetcode Medium)Programming Live with Larry · 17:19 · 75 views
3984. Divisible Game LeetCode Weekly 509 | Maths + Greedy Solution Dry Run with ProofBEASTCODES · 19:36 · 64 views
The problem
You are given an integer array nums of length n.
Alice and Bob are playing a game. Alice chooses:
- An integer
ksuch thatk > 1. - Two integers
landrsuch that0 <= 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 byk, Alice's score increases bynums[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, andr = 3. - All values in
nums[1..3]are divisible by 2, so Alice's score is4 + 6 + 8 = 18, while Bob's score is 0. - The score difference is 18, which is the maximum possible. Among all values of
kthat 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, andr = 2. - The values
nums[0]andnums[2]are divisible by 2, so Alice's score is2 + 2 = 4. The valuenums[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 ofkthat 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 isk = 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. Modulo109 + 7, this equals 1000000005.
Constraints:
1 <= nums.length <= 10001 <= 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.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Brute Force | Exponential | O(n) | Useful for understanding game transitions and validating small test cases |
| Memoized DFS / DP | O(n2) | O(n2) | General solution when repeated states appear frequently |
| Math / Greedy Observation | O(n) | O(1) | Best choice for interviews and large constraints |
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.