{x}
blog image

Maximize Score After N Operations

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:

  • Choose 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.

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 <= 7
  • nums.length == 2 * n
  • 1 <= nums[i] <= 106

Solution Explanation: Maximize Score After N Operations

This problem asks to find the maximum score achievable by performing n operations on an array nums of size 2n. In each operation, we select two numbers, calculate their greatest common divisor (GCD) multiplied by the operation index, and remove them from the array.

The most efficient approach uses bit manipulation, dynamic programming, and state compression.

1. Preprocessing:

  • We first compute a GCD matrix g where g[i][j] stores the GCD of nums[i] and nums[j]. This avoids redundant GCD calculations during the dynamic programming stage.

2. State Representation:

  • We represent the current state of the array using a bitmask. Each bit in the bitmask corresponds to an element in nums. A bit set to 1 indicates the element is still present, while 0 indicates it has been removed. For an array of size 2n, there are 2^(2n) possible states.

3. Dynamic Programming:

  • f[k] stores the maximum score achievable when the array is in state k.
  • The DP transition is as follows:
    • Iterate through all possible states k.
    • If the number of set bits in k (i.e., remaining elements) is even (meaning we can perform an operation), then:
      • Iterate through all pairs of indices i and j where bits i and j are set in k.
      • Calculate the score for this operation: (cnt/2) * g[i][j], where cnt is the number of set bits in k (representing the operation number).
      • Update f[k] to the maximum of its current value and f[k ^ (1 << i) ^ (1 << j)] + (cnt/2) * g[i][j]. This represents the maximum score achievable by reaching state k after removing elements i and j from the previous state k ^ (1 << i) ^ (1 << j).

4. Time and Space Complexity:

  • Time Complexity: O(2^(2n) * (2n)^2). The outer loop iterates through all 2^(2n) possible states. The nested loops iterate through all pairs of indices, which takes O((2n)^2) time.
  • Space Complexity: O(2^(2n)). We need to store the DP table f for all possible states.

Note: The problem's constraint (n <= 7) allows this approach to run within reasonable time. For larger n, more sophisticated techniques would be necessary.

The code implementations provided in Python, Java, C++, Go, and TypeScript all follow this algorithm. The gcd function is a standard Euclidean algorithm for finding the greatest common divisor. The bit manipulation operations (e.g., k.bit_count() in Python, Integer.bitCount() in Java, __builtin_popcount() in C++, bits.OnesCount() in Go, and bitCount() in TypeScript) efficiently count the set bits in the bitmask. The core logic remains consistent across all languages.