Maximize Score After N Operations: Bitmask DP Pattern

You are given nums, an array of positive integers with 2 * n elements. You perform n operations. In the i-th operation (1-indexed), you pick any two elements nums[a] and nums[b] that have not been picked yet, and your score increases by i * gcd(nums[a], nums[b]). Return the maximum score you can achieve after performing all n operations.

This is LeetCode 1799: Maximize Score After N Operations, and it is one of the best problems for learning the bitmask DP technique. The pattern it teaches applies to any problem where you need to track which elements from a small set have been used.

Why this problem matters

Many optimization problems ask you to partition elements into groups and maximize some objective. When the number of elements is small (here, at most 14), bitmask DP lets you enumerate all possible subsets efficiently. This same technique shows up in problems like the Travelling Salesman Problem, assigning tasks to workers, and partitioning sets into groups with constraints.

The tricky part is recognizing when bitmask DP applies. The signal is a small input size (typically n up to 20) combined with a constraint that depends on which elements you have used, not just how many. Once you spot that signal, the bitmask DP template is always the same.

The key insight

The state you need to track is exactly which elements have been used so far. A bitmask of length 2n captures this perfectly: bit i is 1 if nums[i] has been picked, 0 otherwise. The number of 1-bits in the mask tells you how many elements are used, and since you pick two per operation, the operation number is popcount(mask) / 2.

For each state (bitmask), you try every pair of unused elements, compute the GCD, multiply by the current operation number, and take the maximum. The recurrence is:

For every pair (i, j) where both bits are 0 in mask: dp[mask | (1 << i) | (1 << j)] = max(dp[mask | (1 << i) | (1 << j)], dp[mask] + op * gcd(nums[i], nums[j]))

where op = popcount(mask) / 2 + 1.

The solution

from math import gcd

def max_score(nums):
    n = len(nums)
    full = (1 << n) - 1
    dp = [0] * (full + 1)

    for mask in range(full + 1):
        bits = bin(mask).count("1")
        if bits % 2 != 0:
            continue
        op = bits // 2 + 1
        for i in range(n):
            if mask & (1 << i):
                continue
            for j in range(i + 1, n):
                if mask & (1 << j):
                    continue
                new_mask = mask | (1 << i) | (1 << j)
                score = dp[mask] + op * gcd(nums[i], nums[j])
                if score > dp[new_mask]:
                    dp[new_mask] = score

    return dp[full]

Let's walk through what each piece does.

The bitmask mask encodes which elements have been used. We iterate over all possible masks from 0 (nothing used) to full (everything used). For each mask, we only process states where an even number of elements have been used, because elements are always picked in pairs.

The operation number op is derived from the popcount: if 4 elements are used, we have completed 2 operations, so the next operation is number 3. This avoids passing the operation number as a separate parameter.

The inner double loop tries every pair (i, j) of unused elements. For each pair, it computes the new mask with both elements marked as used, calculates the score contribution op * gcd(nums[i], nums[j]), and updates the DP table if this path yields a better score.

The answer lives at dp[full], the maximum score when all elements have been used.

Visual walkthrough

Let's trace through nums = [3, 4, 6, 8] step by step. With n = 2, we need to perform 2 operations, picking a pair of elements each time.

The optimal strategy pairs (3, 6) in operation 1 and (4, 8) in operation 2. The key is that gcd(4, 8) = 4 is the largest GCD among all pairs, so assigning it to operation 2 (with multiplier 2) maximizes the total. The bitmask DP explores all possible pairings and finds this automatically.

Complexity analysis

Time is O(2^(2n) * n^2). There are 2^(2n) possible masks. For each mask, we try all pairs of unused elements, which is at most O(n^2) pairs. With 2n up to 14, this gives 2^14 * 49 = roughly 800,000 operations, which is very fast.

Space is O(2^(2n)) for the DP array. Each entry stores a single integer (the best score for that mask). With 2n = 14, the array has 16,384 entries.

The building blocks

1. Bitmask subset enumeration

The core pattern of iterating over all subsets and checking membership:

for mask in range(1 << n):
    for i in range(n):
        if not (mask & (1 << i)):
            pass

This is the foundation of bitmask DP. You iterate over every possible subset (represented as an integer from 0 to 2^n - 1) and check whether element i is in the subset by testing mask & (1 << i). This pattern appears in any problem that tracks "which elements have been used" as the DP state, including Travelling Salesman, task assignment, and set partitioning problems.

2. GCD as a pairing metric

The gcd function from Python's math module computes the greatest common divisor. In this problem, gcd serves as the "value" of a pairing:

from math import gcd

g = gcd(nums[i], nums[j])

Precomputing a table of gcd(nums[i], nums[j]) for all pairs can speed things up slightly, but with n up to 7 (14 elements), it is not necessary. The key observation is that gcd is symmetric and can produce values much larger than 1 when elements share factors, which is why pairing strategy matters.

3. Deriving operation count from popcount

Instead of tracking the operation number as a separate variable, derive it from the mask:

op = bin(mask).count("1") // 2 + 1

This trick works whenever each "step" consumes a fixed number of elements. For problems where you pick one element per step, the operation number is just the popcount. For pair-based problems like this one, divide by 2. Embedding information in the mask keeps your DP state compact.

Edge cases

• Two elements (n=1). Only one pair exists. The answer is 1 * gcd(nums[0], nums[1]).
• All elements equal. Every pair has the same gcd (the common value). The answer is the sum of i * value for i from 1 to n, which is value * n * (n + 1) / 2.
• All elements coprime. Every gcd is 1. The answer is 1 + 2 + ... + n = n * (n + 1) / 2 regardless of pairing.
• Maximum size (2n = 14). The bitmask has 14 bits, giving 16,384 states. The solution runs comfortably within time limits.
• Elements with large GCD. When two elements share a large factor (e.g., 12 and 24 with gcd 12), assigning that pair to a later operation with a higher multiplier gives a big score boost.

From understanding to recall

You have seen how bitmask DP works: represent the set of used elements as a bitmask, iterate over all masks, try all valid transitions, and track the maximum. The logic is clean and the code is compact. But writing it from scratch in an interview requires you to remember several details.

Which direction do you iterate? (Forward, from 0 to full.) How do you compute the operation number? (Popcount divided by 2, plus 1.) How do you mark two elements as used? (OR the mask with both bit positions.) These are recall gaps, not conceptual ones, and they trip people up under pressure.

Spaced repetition closes those gaps. You practice writing the bitmask iteration, the pair enumeration, and the DP update from memory at increasing intervals. After a few rounds, you see "small n, track which elements are used" and the bitmask DP template flows out automatically.

Related posts

• Number of Squareful Arrays - Backtracking with bitmask-like state tracking to count valid permutations of a small array
• Subsets - The foundational subset enumeration problem that teaches you to think in terms of bitmasks
• Edit Distance - Classic DP on two dimensions, showing how to build a DP table and trace transitions

CodeBricks breaks Maximize Score After N Operations into its bitmask DP enumeration and GCD pairing building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a bitmask DP problem shows up in your interview, you do not think about it. You just write it.