Maximize Score After N Operations

Hard
1347.

Maximize Score After N Operations

Maximize Score After N Operations is a hard coding problem on dynamic programming, math and number theory, asked in Amazon, Google and Sprinklr interviews.

You are given an array nums of 2 * n positive integers and must perform exactly n operations. In the i-th operation (1-indexed) you choose two remaining elements x and y, gain i * gcd(x, y) points, and remove both from the array.

Return the maximum total score after all n operations.

Example 1

Input
nums = [6,9]
Output
3
Explanation
One operation: `1 * gcd(6, 9) = 3`.

Example 2

Input
nums = [4,6,8,12]
Output
16
Explanation
First (4, 8) for `1 * 4`, then (6, 12) for `2 * 6`.

Example 3

Input
nums = [5,5,5,5]
Output
15

Constraints

  • 1 <= n <= 7
  • nums.length == 2 * n
  • 1 <= nums[i] <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxScore = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximize Score After N Operations — Problem & Solution

Maximize Score After N Operations solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Maximize Score After N Operations is a hard coding problem on dynamic programming, math and number theory, asked in Amazon, Google and Sprinklr interviews.

Problem statement

You are given an array nums of 2 * n positive integers and must perform exactly n operations. In the i-th operation (1-indexed) you choose two remaining elements x and y, gain i * gcd(x, y) points, and remove both from the array.

Return the maximum total score after all n operations.

Example 1

Input: nums = [6,9]
Output: 3
Explanation: One operation: `1 * gcd(6, 9) = 3`.

Example 2

Input: nums = [4,6,8,12]
Output: 16
Explanation: First (4, 8) for `1 * 4`, then (6, 12) for `2 * 6`.

Example 3

Input: nums = [5,5,5,5]
Output: 15

Constraints

  • 1 <= n <= 7
  • nums.length == 2 * n
  • 1 <= nums[i] <= 10^6

Hints for Maximize Score After N Operations

  1. Hint 1

    With at most 14 elements, the set of removed elements fits in a bitmask, and the number of the next operation is half its popcount plus one.

  2. Hint 2

    Let dp[mask] be the best score after removing exactly the elements in mask (an even number of them).

  3. Hint 3

    From mask, try every pair (i, j) of remaining elements: dp[mask | bit(i) | bit(j)] = max(…, dp[mask] + op * gcd(nums[i], nums[j])), with the gcds precomputed.

How to solve Maximize Score After N Operations

The order of operations matters only through the multiplier, which equals one plus the number of pairs already removed — that is, it is fixed by the mask. So a DP over masks of removed elements captures the whole problem.

Approach

  1. Precompute g[i][j] = gcd(nums[i], nums[j]) for all pairs.
  2. Set dp[0] = 0 and visit masks in increasing order, skipping masks with an odd popcount.
  3. For a mask, op = popcount(mask) / 2 + 1. For each pair i < j of elements not in mask, update dp[mask | 1<<i | 1<<j] with dp[mask] + op * g[i][j].
  4. Return dp[2^(2n) - 1].

Why it works

Any sequence of operations removes pairs one by one, passing through masks with 2, 4, … elements, and the k-th removal always earns k times its gcd. The best way to finish from a given mask does not depend on how that mask was reached, so storing the best score per mask is exact, and every possible sequence is a path the DP examines.

Complexity

  • Time — O(4^n · n²)
  • Space — O(4^n)

Pitfalls

  • Pairing the lowest free element first (a common speed-up for matching) is wrong here: it fixes the order of the pairs, and order changes the multipliers.
  • The multiplier comes from how many pairs were already removed, not from the indices of the elements.
  • Precompute the gcds — recomputing them inside the DP loop is the slow part otherwise.

Reference solution

Python

from typing import List
from math import gcd

def maxScore(nums: List[int]) -> int:
    m = len(nums)
    g = [[gcd(nums[i], nums[j]) for j in range(m)] for i in range(m)]
    full = 1 << m
    dp = [0] * full
    for mask in range(full):
        c = bin(mask).count("1")
        if c & 1:
            continue
        op = c // 2 + 1
        base = dp[mask]
        for i in range(m):
            if (mask >> i) & 1:
                continue
            for j in range(i + 1, m):
                if (mask >> j) & 1:
                    continue
                nm = mask | (1 << i) | (1 << j)
                v = base + op * g[i][j]
                if v > dp[nm]:
                    dp[nm] = v
    return dp[full - 1]

Java

public static int maxScore(int[] nums) {
    int m = nums.length, full = 1 << m;
    int[][] g = new int[m][m];
    for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) g[i][j] = msnGcd(nums[i], nums[j]);
    int[] dp = new int[full];
    for (int mask = 0; mask < full; mask++) {
        int c = Integer.bitCount(mask);
        if ((c & 1) == 1) continue;
        int op = c / 2 + 1;
        for (int a = 0; a < m; a++) {
            if ((mask & (1 << a)) != 0) continue;
            for (int b = a + 1; b < m; b++) {
                if ((mask & (1 << b)) != 0) continue;
                int nm = mask | (1 << a) | (1 << b);
                dp[nm] = Math.max(dp[nm], dp[mask] + op * g[a][b]);
            }
        }
    }
    return dp[full - 1];
}

static int msnGcd(int a, int b) {
    while (b != 0) { int t = a % b; a = b; b = t; }
    return a;
}

C++

static int msnGcd(int a, int b) {
    while (b) { int t = a % b; a = b; b = t; }
    return a;
}

int maxScore(vector<int>& nums) {
    int m = nums.size(), full = 1 << m;
    vector<vector<int>> g(m, vector<int>(m));
    for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) g[i][j] = msnGcd(nums[i], nums[j]);
    vector<int> dp(full, 0);
    for (int mask = 0; mask < full; mask++) {
        int c = __builtin_popcount(mask);
        if (c & 1) continue;
        int op = c / 2 + 1;
        for (int a = 0; a < m; a++) {
            if (mask & (1 << a)) continue;
            for (int b = a + 1; b < m; b++) {
                if (mask & (1 << b)) continue;
                int nm = mask | (1 << a) | (1 << b);
                dp[nm] = max(dp[nm], dp[mask] + op * g[a][b]);
            }
        }
    }
    return dp[full - 1];
}

JavaScript

var maxScore = function(nums) {
    var m = nums.length, full = 1 << m;
    var gcd = function(a, b) { while (b) { var t = a % b; a = b; b = t; } return a; };
    var g = [];
    for (var i = 0; i < m; i++) {
        g.push([]);
        for (var j = 0; j < m; j++) g[i].push(gcd(nums[i], nums[j]));
    }
    var dp = new Array(full).fill(0);
    for (var mask = 0; mask < full; mask++) {
        var c = 0;
        for (var x = mask; x; x >>= 1) c += x & 1;
        if (c & 1) continue;
        var op = c / 2 + 1;
        for (var a = 0; a < m; a++) {
            if (mask & (1 << a)) continue;
            for (var b = a + 1; b < m; b++) {
                if (mask & (1 << b)) continue;
                var nm = mask | (1 << a) | (1 << b), v = dp[mask] + op * g[a][b];
                if (v > dp[nm]) dp[nm] = v;
            }
        }
    }
    return dp[full - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming