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.
This approach uses backtracking to explore all possible pairs of elements for the operations. The goal is to maximize the sum of scores obtained from each operation. To optimize the solution, pruning is applied by avoiding redundant calculations using a memoization table. By systematically trying all combinations, we gradually eliminate suboptimal solutions and select the maximal score possible.
This C implementation uses bit manipulation to keep track of used numbers and compute GCD pairs selectively. The recursive function 'backtrack' explores all pairs of elements, marking them as used and calculating their scores. The result is updated if a higher score is found. Memoization is added to store intermediate results to prevent recalculations.
Time Complexity: O((2n)! / 2^n), the approach explores all possible combinations of pairs.
Space Complexity: O(2^n), for memoization array to store intermediate results.
This approach leverages dynamic programming along with bit masking to compute the maximum score possible. The idea is to use a DP state to remember the best score possible with a certain combination of pairs already taken. The state is determined by a bitmask which indicates the taken pairs. Recursively calculate the maximum possible score, storing intermediate results to avoid repeated calculations.
The solution maintains a DP array where each entry dp[mask] stores the maximum score achievable for a set of already chosen pairs defined by 'mask'. The nested loops iterate over possible pairings, dynamically updating the DP array.
Time Complexity: O(n^2 * 2^n), where n is the number of elements in 'nums'.
Space Complexity: O(2^n) for the DP array.
We can preprocess to get the greatest common divisor of any two numbers in the array nums, stored in the two-dimensional array g, where g[i][j] represents the greatest common divisor of nums[i] and nums[j].
Then define f[k] to represent the maximum score that can be obtained when the state after the current operation is k. Suppose m is the number of elements in the array nums, then there are a total of 2^m states, that is, the range of k is [0, 2^m - 1].
Enumerate all states from small to large, for each state k, first determine whether the number of 1s in the binary bits of this state cnt is even, if so, perform the following operations:
Enumerate the positions where the binary bits in k are 1, suppose they are i and j, then the elements at positions i and j can perform one operation, and the score that can be obtained at this time is \frac{cnt}{2} times g[i][j], update the maximum value of f[k].
The final answer is f[2^m - 1].
The time complexity is O(2^m times m^2), and the space complexity is O(2^m). Here, m is the number of elements in the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Backtracking with Pruning | Time Complexity: O((2n)! / 2^n), the approach explores all possible combinations of pairs. |
| Approach 2: Dynamic Programming with Bitmask | Time Complexity: O(n^2 * 2^n), where n is the number of elements in 'nums'. |
| State Compression + Dynamic Programming | — |
| 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 |
Maximize Score after N Operations - Leetcode 1799 - Python • NeetCodeIO • 9,820 views views
Watch 9 more video solutions →Practice Maximize Score After N Operations with our built-in code editor and test cases.
Practice on FleetCode