Maximize Score After N Operations - Leetcode Solution

Problem:

You are given nums, an array of integers of length 2 * n. You must perform n operations on this array.

In the ith operation (1-indexed), you will:

Select two elements, x and y. Receive a score of i * gcd(x, y). Remove x and y from nums. Return the maximum score you can receive after performing n operations.

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)) = 3
• (2 * gcd(4, 8)) = 8
• Total score is 11.

Constraints:

• 1 <= nums.length <= 7
• 2 <= nums.length <= 15
• nums.length % 2 == 0
• 1 <= nums[i] <= 10^6

Solution:

The problem can be solved using dynamic programming to enumerate all possible pairs of integers in nums and calculate the score for each combination. We can then keep track of the maximum score for each step by maximizing the score of each operation.

First, we need a function to calculate the greatest common divisor (GCD) of two numbers. We can use Euclid's algorithm to do this:

def gcd(a, b): if b == 0: return a return gcd(b, a % b)

Next, we need a function to calculate the score of a given pair of integers. We can iterate through all the possible values of i and multiply by the GCD:

def score(nums, i, x, y): return i * gcd(nums[x], nums[y])

Now we can define a recursive function to calculate the maximum score for each step. We start with an empty list of pairs and iterate through all the possible pairs of integers in nums. For each pair, we append it to the list and recursively call the function with the remaining elements of nums and the updated list of pairs. We calculate the score for each possible pair and keep track of the maximum score:

def solve(nums, pairs, memo): if len(pairs) == len(nums) // 2: return 0 state = tuple(nums), tuple(pairs) if state in memo: return memo[state] ans = 0 for i in range(len(nums)): for j in range(i + 1, len(nums)): if i not in [x for p in pairs for x in p] and j not in [x for p in pairs for x in p]: new_nums = [nums[k] for k in range(len(nums)) if k != i and k != j] new_pairs = pairs + [[i, j]] ans = max(ans, score(nums, len(pairs) + 1, i, j) + solve(new_nums, new_pairs, memo)) memo[state] = ans return ans

Finally, we can call the solve function with the initial values of nums, an empty list of pairs, and an empty memoization dictionary:

class Solution: def maxScore(self, nums: List[int]) -> int: return solve(nums, [], {})

1