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] <= 106This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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'. |
Apply Operations to Maximize Score - Leetcode 2818 - Python • NeetCodeIO • 9,780 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