Watch 10 video solutions for Maximize Score After N Operations, a hard level problem involving Array, Math, Dynamic Programming. This walkthrough by NeetCodeIO has 9,820 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given nums, an array of positive integers of size 2 * n. You must perform n operations on this array.
In the ith operation (1-indexed), you will:
x and y.i * gcd(x, y).x and y from nums.Return the maximum score you can receive after performing n operations.
The function gcd(x, y) is the greatest common divisor of x and y.
Example 1:
Input: nums = [1,2] Output: 1 Explanation: The optimal choice of operations is: (1 * gcd(1, 2)) = 1
Example 2:
Input: nums = [3,4,6,8] Output: 11 Explanation: The optimal choice of operations is: (1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11
Example 3:
Input: nums = [1,2,3,4,5,6] Output: 14 Explanation: The optimal choice of operations is: (1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14
Constraints:
1 <= n <= 7nums.length == 2 * n1 <= nums[i] <= 106Problem Overview: You are given 2n integers. In each operation, pick two unused numbers, compute their gcd, and add operation_index × gcd to the score. After n operations all numbers are used. The goal is to choose pairings that maximize the total score.
Approach 1: Backtracking with Pruning (Time: O((2n)! / (2^n · n!)), Space: O(n))
This approach tries every possible way to form pairs. At each step you iterate through unused numbers, pick two, compute their gcd, and recursively continue with the remaining elements. The operation number increases each time, so earlier choices influence the final score significantly. Pruning helps slightly: skip already-used indices and avoid recomputing states where the same numbers remain. The algorithm essentially enumerates all pair combinations, which grows quickly but still works because 2n ≤ 14. The method directly demonstrates the pairing logic and uses recursion with a visited array.
Approach 2: Dynamic Programming with Bitmask (Time: O(m² · 2^m), Space: O(2^m))
The optimized solution represents which numbers are already used with a bitmask of length m = 2n. Each DP state mask stores the maximum score achievable using exactly those elements. Count the number of set bits in the mask to determine the current operation number. For every state, iterate through pairs of unused indices, compute their gcd, and transition to a new mask where both bits are set. Precomputing pairwise gcd values speeds up transitions. This transforms exponential pairing into structured dynamic programming over subsets, a common pattern in bitmask problems. The scoring rule directly leverages number theory through the gcd operation.
Recommended for interviews: Dynamic Programming with Bitmask is the expected solution. Brute-force backtracking shows you understand the pairing structure, but the DP version demonstrates optimization using subset states and avoids recomputing equivalent configurations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Pruning | O((2n)! / (2^n · n!)) | O(n) | When demonstrating the brute-force pairing logic or when constraints are very small |
| Dynamic Programming with Bitmask | O(m² · 2^m) | O(2^m) | General optimal solution for subset pairing problems with m ≤ 14 elements |