Maximize Score After N Operations

Problem Description

Given an array nums of 2 * n positive integers, perform n operations where in the iᵗʰ operation you:

• Pick any two remaining numbers x and y.
• Gain a score of i * gcd(x, y) (where gcd is the greatest common divisor).
• Remove x and y from nums. Return the maximum score possible after exactly n operations.

Key Insights

• Use a bitmask or state representation to track which numbers have been picked.
• With n up to 7 (i.e., nums size up to 14), the total number of states (2^(2*n)) is manageable.
• Use recursion with memoization (DP) to avoid recalculating results for the same state.
• Pre-calculate gcd for each pair of numbers to optimize the inner loop.
• The order of operations matters because each operation multiplies the gcd by the current operation index.

Space and Time Complexity

Time Complexity: O(2^(2n) * (2n)^2) – since for each state represented by a bitmask, we attempt pairing available numbers. Space Complexity: O(2^(2*n)) – for the memoization cache.

Solution

We use a bitmask to represent the state of the array (each bit represents whether an element is used). We perform a DFS to try all possible pairs of unused numbers. At each recursive call:

1. Count the number of operations already performed (derived from the number of bits set).
2. Identify the operation multiplier as (number of operations performed + 1).
3. For every pair of unused numbers, compute the added score from the pair (multiplier * gcd(value1, value2)).
4. Recursively compute the maximum score from the new state after marking these two elements as used.
5. Use memoization to cache and quickly return the computed result for a given bitmask state. This algorithm explores all pairing combinations ensuring that we maximize the total score.

Code Solutions