Divisible Game - Video Solutions
Divisible Game | Leetcode 3984 | Kadanes Algo | Number Theory
Divisible Game - Video Solution
Watch 5 video solutions for Divisible Game, a medium level problem involving Array, Math, Dynamic Programming. This walkthrough by Techdose has 452 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
Complexity 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 |