Maximize Score After N Operations

hard bitmask dp gcd

Problem

Pick numbers from 2n integers two at a time; the kth pair (1-indexed) contributes k · gcd(a, b). Return the maximum total.

Inputnums = [1,2,3,4,5,6]

Output14

Pairs (1,5),(2,4),(3,6) → 1·gcd(1,5)=1, 2·gcd(2,4)=4, 3·gcd(3,6)=9 → 14.

nums (even count)

from math import gcd
def max_score(nums):
    n = len(nums)
    full = (1 << n) - 1
    memo = {}
    def solve(mask, k):
        if mask == full: return 0
        if (mask, k) in memo: return memo[(mask, k)]
        best = 0
        for i in range(n):
            if mask & (1 << i): continue
            for j in range(i + 1, n):
                if mask & (1 << j): continue
                nm = mask | (1 << i) | (1 << j)
                best = max(best, k * gcd(nums[i], nums[j]) + solve(nm, k + 1))
        memo[(mask, k)] = best
        return best
    return solve(0, 1)

function gcd(a, b) { while (b) { [a, b] = [b, a % b]; } return a; }
function maxScore(nums) {
  const n = nums.length, full = (1 << n) - 1;
  const memo = new Map();
  function solve(mask, k) {
    if (mask === full) return 0;
    const key = mask * 16 + k;
    if (memo.has(key)) return memo.get(key);
    let best = 0;
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) continue;
      for (let j = i + 1; j < n; j++) {
        if (mask & (1 << j)) continue;
        const nm = mask | (1 << i) | (1 << j);
        best = Math.max(best, k * gcd(nums[i], nums[j]) + solve(nm, k + 1));
      }
    }
    memo.set(key, best);
    return best;
  }
  return solve(0, 1);
}

class Solution {
    int[] memo;
    int[] nums; int n;
    int gcd(int a, int b) { while (b != 0) { int t = a % b; a = b; b = t; } return a; }
    int solve(int mask, int k) {
        if (mask == (1 << n) - 1) return 0;
        int key = mask;
        if (memo[key] >= 0) return memo[key];
        int best = 0;
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) continue;
            for (int j = i + 1; j < n; j++) {
                if ((mask & (1 << j)) != 0) continue;
                int nm = mask | (1 << i) | (1 << j);
                best = Math.max(best, k * gcd(nums[i], nums[j]) + solve(nm, k + 1));
            }
        }
        memo[key] = best;
        return best;
    }
    public int maxScore(int[] nums) {
        this.nums = nums; this.n = nums.length;
        memo = new int[1 << n]; Arrays.fill(memo, -1);
        return solve(0, 1);
    }
}

class Solution { public:
    vector<int> memo; vector<int> nums; int n;
    int gcd(int a, int b) { while (b) { int t = a % b; a = b; b = t; } return a; }
    int solve(int mask, int k) {
        if (mask == (1 << n) - 1) return 0;
        if (memo[mask] >= 0) return memo[mask];
        int best = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) continue;
            for (int j = i + 1; j < n; j++) {
                if (mask & (1 << j)) continue;
                int nm = mask | (1 << i) | (1 << j);
                best = max(best, k * gcd(nums[i], nums[j]) + solve(nm, k + 1));
            }
        }
        return memo[mask] = best;
    }
    int maxScore(vector<int>& a) { nums = a; n = a.size(); memo.assign(1 << n, -1); return solve(0, 1); }
};

Explanation

We pair up 2n numbers, and the kth pair we form earns k · gcd(a, b). Since which numbers are still available is all that matters, we track that set with a bitmask — bit i set means number i is already used.

The recursion solve(mask, k) answers: given the used set mask and that we are about to form the kth pair, what is the best score from here on? We try every unused pair (i, j), add k · gcd(nums[i], nums[j]), mark them used, and recurse for pair k+1.

We keep the maximum over all pair choices. When every number is used (mask is full), there is nothing left to earn, so we return 0.

Because the same mask can be reached by many different orders of picking, we memoize on it to avoid recomputing. The multiplier k is implied by how many bits are already set, so the cached answer per mask is well defined.

Example: for nums = [1,2,3,4,5,6], pairing (1,5),(2,4),(3,6) earns 1·1 + 2·2 + 3·3 = 14, the maximum.

Time: O(2^n · n²) Space: O(2^n)