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.
- Difficulty: Hard
- Topics: Dynamic Programming, Math, Number Theory, Bitmask
- Asked at: Amazon, Google, Sprinklr
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 7nums.length == 2 * n1 <= nums[i] <= 10^6
Hints for Maximize Score After N Operations
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.
Hint 2
Let
dp[mask]be the best score after removing exactly the elements inmask(an even number of them).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
- Precompute
g[i][j] = gcd(nums[i], nums[j])for all pairs. - Set
dp[0] = 0and visit masks in increasing order, skipping masks with an odd popcount. - For a mask,
op = popcount(mask) / 2 + 1. For each pairi < jof elements not inmask, updatedp[mask | 1<<i | 1<<j]withdp[mask] + op * g[i][j]. - 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