Problem Description

You are given an array nums of length 2 * n where n is a positive integer. In each of n operations, you select two unused elements from nums, calculate their greatest common divisor (GCD), multiply it by the operation number (starting from 1), and add the result to your total score. Once selected, the two elements cannot be used again. Your task is to maximize the total score after performing all n operations.

• Each element in nums can be used only once.
• You must perform exactly n operations, pairing up all elements.
• There is only one valid solution for each input, but the order of operations and pairings affects the result.

The goal is to find the maximum possible score obtainable by optimally pairing and ordering the operations.

Thought Process

The problem asks us to maximize a sum where each term is the GCD of a pair of unused numbers, multiplied by the operation number. At first glance, it is tempting to try all possible pairings and all possible orders, but this quickly becomes infeasible as the array grows.

A brute-force approach would involve generating all possible ways to pair up the numbers, then for each pairing, try all possible orders of performing the operations. Since the number of pairings grows rapidly (roughly as the double factorial), this approach does not scale.

To optimize, we look for overlapping subproblems and optimal substructure, which suggests dynamic programming (DP). We need a way to efficiently represent which numbers have been used, and to remember the best score we can get from each state. Using a bitmask to represent the set of used/unused numbers is a powerful technique here.

Solution Approach

We use dynamic programming with bitmasking to solve this problem efficiently. Here is the step-by-step approach:

1. Bitmask Representation:
   • Since there are 2n elements, we use a bitmask of length 2n to indicate which numbers have been used (1) and which are still available (0).
2. Recursive Function:
   • We define a recursive function dp(mask), where mask indicates the current set of used numbers.
   • For each call, we look for two unused numbers (i.e., bits not set in mask), pair them, and recursively compute the best score for the updated mask.
3. Operation Number:
   • The operation number is determined by how many numbers have already been used: op = used_count // 2 + 1.
4. Memoization:
   • To avoid recomputation, we store the best score for each mask in a memoization table (e.g., a hash map).
5. Base Case:
   • When all numbers have been used (mask has all bits set), we return 0.
6. Precompute GCDs:
   • To speed up calculation, we precompute the GCD for every possible pair in nums.
7. Try All Pairs:
   • For each state, try all possible pairs of unused numbers, compute the score if we use them now, and recurse.

This approach ensures that we only compute each state once, and by always choosing the best available option, we maximize the total score.

Example Walkthrough

Let's consider an example: nums = [1, 2, 3, 4]

• There are 4 numbers, so n = 2 operations.
• Possible pairings:
  • (1,2) and (3,4)
  • (1,3) and (2,4)
  • (1,4) and (2,3)
• For each pairing, the order of operations matters. For example, pairing (1,4) and (2,3):
  • First operation: GCD(1,4) = 1, operation number = 1, score = 1 * 1 = 1
  • Second operation: GCD(2,3) = 1, operation number = 2, score = 1 * 2 = 2
  • Total score = 1 + 2 = 3
• But if we do (2,4) first: GCD(2,4) = 2, score = 2 * 1 = 2. Then (1,3): GCD(1,3) = 1, score = 1 * 2 = 2. Total = 2 + 2 = 4.
• The best is to pair (2,4) and (1,3), and do (2,4) first, getting a score of 4.

The DP with bitmasking will try all possible pairings and orders, but only once per unique state, ensuring efficiency.

Time and Space Complexity

• Brute-force:
  • The number of ways to pair 2n elements is (2n)! / (2^n * n!), and for each pairing, there are n! orders. This is extremely large even for small n.
• Optimized DP with Bitmask:
  • There are 2^{2n} possible masks (states), but only those with even numbers of bits set are relevant.
  • For each state, we try all pairs of unused numbers, which is at most O(n^2) per state.
  • Overall complexity is O( (2^{2n}) * n^2 ). For n ≤ 7 (i.e., nums length up to 14), this is feasible.
  • Space complexity is O(2^{2n}) for the memoization table.

Summary

To maximize the score after n operations, we use dynamic programming and bitmasking to efficiently explore all possible pairings and orders. By representing used numbers with a bitmask and memoizing results, we avoid redundant computation and ensure we always choose the best available move. Precomputing GCDs further optimizes our solution. This approach elegantly solves a problem that is otherwise intractable with brute force.

Code Implementation

from math import gcd
from functools import lru_cache

class Solution:
    def maxScore(self, nums):
        n = len(nums) // 2
        gcds = {}
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                gcds[(i, j)] = gcd(nums[i], nums[j])

        @lru_cache(maxsize=None)
        def dp(mask):
            used = bin(mask).count('1')
            if used == len(nums):
                return 0
            op = used // 2 + 1
            max_score = 0
            for i in range(len(nums)):
                if not (mask & (1 << i)):
                    for j in range(i + 1, len(nums)):
                        if not (mask & (1 << j)):
                            new_mask = mask | (1 << i) | (1 << j)
                            score = op * gcds[(i, j)] + dp(new_mask)
                            if score > max_score:
                                max_score = score
            return max_score

        return dp(0)
      

#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxScore(vector<int>& nums) {
        int n = nums.size() / 2;
        int N = nums.size();
        vector<vector<int>> gcds(N, vector<int>(N, 0));
        for (int i = 0; i < N; ++i)
            for (int j = i + 1; j < N; ++j)
                gcds[i][j] = __gcd(nums[i], nums[j]);

        unordered_map<int, int> memo;

        function<int(int)> dp = [&](int mask) {
            if (memo.count(mask)) return memo[mask];
            int used = __builtin_popcount(mask);
            if (used == N) return 0;
            int op = used / 2 + 1;
            int max_score = 0;
            for (int i = 0; i < N; ++i) {
                if (!(mask & (1 << i))) {
                    for (int j = i + 1; j < N; ++j) {
                        if (!(mask & (1 << j))) {
                            int new_mask = mask | (1 << i) | (1 << j);
                            int score = op * gcds[i][j] + dp(new_mask);
                            max_score = max(max_score, score);
                        }
                    }
                }
            }
            return memo[mask] = max_score;
        };

        return dp(0);
    }
};
      

import java.util.*;

class Solution {
    public int maxScore(int[] nums) {
        int n = nums.length / 2;
        int N = nums.length;
        int[][] gcds = new int[N][N];
        for (int i = 0; i < N; ++i)
            for (int j = i + 1; j < N; ++j)
                gcds[i][j] = gcd(nums[i], nums[j]);

        Map<Integer, Integer> memo = new HashMap<>();

        return dp(0, nums, gcds, memo, N);
    }

    private int dp(int mask, int[] nums, int[][] gcds, Map<Integer, Integer> memo, int N) {
        if (memo.containsKey(mask)) return memo.get(mask);
        int used = Integer.bitCount(mask);
        if (used == N) return 0;
        int op = used / 2 + 1;
        int max_score = 0;
        for (int i = 0; i < N; ++i) {
            if ((mask & (1 << i)) == 0) {
                for (int j = i + 1; j < N; ++j) {
                    if ((mask & (1 << j)) == 0) {
                        int new_mask = mask | (1 << i) | (1 << j);
                        int score = op * gcds[i][j] + dp(new_mask, nums, gcds, memo, N);
                        if (score > max_score) max_score = score;
                    }
                }
            }
        }
        memo.put(mask, max_score);
        return max_score;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
      

var maxScore = function(nums) {
    const n = nums.length / 2;
    const N = nums.length;
    const gcds = Array.from({length: N}, () => Array(N).fill(0));
    for (let i = 0; i < N; ++i)
        for (let j = i + 1; j < N; ++j)
            gcds[i][j] = gcd(nums[i], nums[j]);

    const memo = new Map();

    function dp(mask) {
        if (memo.has(mask)) return memo.get(mask);
        let used = 0, tmp = mask;
        while (tmp) {
            used += tmp & 1;
            tmp >>= 1;
        }
        if (used === N) return 0;
        const op = Math.floor(used / 2) + 1;
        let max_score = 0;
        for (let i = 0; i < N; ++i) {
            if (!(mask & (1 << i))) {
                for (let j = i + 1; j < N; ++j) {
                    if (!(mask & (1 << j))) {
                        const new_mask = mask | (1 << i) | (1 << j);
                        const score = op * gcds[i][j] + dp(new_mask);
                        if (score > max_score) max_score = score;
                    }
                }
            }
        }
        memo.set(mask, max_score);
        return max_score;
    }

    function gcd(a, b) {
        while (b) {
            [a, b] = [b, a % b];
        }
        return a;
    }

    return dp(0);
};