Watch 5 video solutions for Divisible Game, a medium level problem. This walkthrough by Techdose has 452 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums of length n.
Alice and Bob are playing a game. Alice chooses:
k such that k > 1.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):
nums[i] is divisible by k, Alice's score increases by nums[i].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:
k = 2, l = 1, and r = 3.nums[1..3] are divisible by 2, so Alice's score is 4 + 6 + 8 = 18, while Bob's score is 0.k that achieve this score difference, the smallest is 2.18 * 2 = 36.Example 2:
Input: nums = [2,1,2]
Output: 6
Explanation:
k = 2, l = 0, and r = 2.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.4 - 1 = 3, which is the maximum possible. Among all values of k that achieve this score difference, the smallest is 2.3 * 2 = 6.Example 3:
Input: nums = [1]
Output: 1000000005
Explanation:
k > 1. The smallest possible choice is k = 2.nums[0] is not divisible by 2, Alice's score is 0, while Bob's score is 1.-1 * 2 = -2. Modulo 109 + 7, this equals 1000000005.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 106Problem 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.
| 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 |