LeetCode 1799 - Maximize Score After N Operations

The problem asks us to maximize the total score obtained by performing n operations on an array nums of size 2 n.

leetcodehardarraymathdynamic-programmingbacktrackingbit-manipulationnumber-theorybitmask

LeetCode Problem 1799

Difficulty: 🔴 Hard
Topics: Array, Math, Dynamic Programming, Backtracking, Bit Manipulation, Number Theory, Bitmask

Solution

Problem Understanding

The problem asks us to maximize the total score obtained by performing n operations on an array nums of size 2 * n. In each operation, you select two elements from the array, calculate the greatest common divisor (GCD) of the two elements, multiply it by the operation index (1-indexed), add it to your score, and remove those two elements from the array. The goal is to determine the sequence of element pairings that yields the maximum possible score after all operations are completed.

The input nums is an array of positive integers. The output is a single integer representing the maximum score achievable after performing n operations. Given the constraints (1 <= n <= 7, nums.length == 2 * n, 1 <= nums[i] <= 10^6), the array is relatively small, but the number of possible pairings grows factorially. This makes a brute-force approach infeasible for larger values of n.

Key edge cases to consider include arrays where all elements are the same (the GCD is maximal for all pairs), arrays with prime numbers (GCDs are likely 1), and arrays where strategic pairing is crucial to maximize the weighted score.

Approaches

A brute-force approach would generate all possible sequences of pairings and calculate the score for each. This guarantees the correct answer but is computationally expensive because for 2 * n elements, the number of unique pairings is (2 * n)! / (2^n * n!), which grows extremely fast. This approach is only feasible for very small n.

The optimal approach uses dynamic programming with bitmasking. We represent the state of the array using a bitmask where each bit indicates whether an element is still available. For each state, we try all possible pairs of unused elements, compute the score for that operation, and recursively find the maximum score for the remaining elements. Memoization stores previously computed states to avoid redundant calculations.

Approach Time Complexity Space Complexity Notes
Brute Force O((2n)!) O((2n)!) Generate all pairings and compute score, infeasible for n > 4
Optimal (DP + Bitmask) O(4^n * n^2) O(2^(2n)) Bitmask DP tracks used elements; recursive memoization avoids recomputation

Algorithm Walkthrough

  1. Precompute all possible pair GCDs. Since the array has 2 * n elements, this requires computing GCD for all pairs, which allows fast lookup during recursion.
  2. Define a recursive function dfs(mask) where mask is a bitmask representing the used elements. A bit set to 1 means the element is used, 0 means it is available.
  3. If all elements are used (mask == (1 << 2*n) - 1), return 0 because no further score can be obtained.
  4. Count the number of elements already used (the number of bits set in mask) to determine the current operation index: op_index = used_count // 2 + 1.
  5. Iterate over all pairs of unused elements (i, j). For each pair:

a. Compute the new mask with both elements marked as used.

b. Calculate the score for this operation: op_index * gcd(nums[i], nums[j]).

c. Recursively call dfs(new_mask) to get the maximum score for the remaining elements.

d. Track the maximum score across all pairs. 6. Memoize the result for mask to avoid recalculating. 7. Return the maximum score starting from mask = 0.

Why it works: The DP with bitmask ensures that every subset of the array is considered exactly once. By storing results for each mask, we avoid redundant calculations. The operation index is correctly incremented because it depends on the number of elements used so far. This guarantees that all pairings are explored optimally.

Python Solution

from math import gcd
from functools import lru_cache
from typing import List

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        n = len(nums) // 2
        
        # Precompute all pairwise GCDs
        pair_gcd = [[0] * (2*n) for _ in range(2*n)]
        for i in range(2*n):
            for j in range(i+1, 2*n):
                pair_gcd[i][j] = gcd(nums[i], nums[j])
        
        @lru_cache(None)
        def dfs(mask: int) -> int:
            used_count = bin(mask).count("1")
            if used_count == 2 * n:
                return 0
            op_index = used_count // 2 + 1
            max_score = 0
            for i in range(2*n):
                if not (mask & (1 << i)):
                    for j in range(i+1, 2*n):
                        if not (mask & (1 << j)):
                            new_mask = mask | (1 << i) | (1 << j)
                            score = op_index * pair_gcd[i][j] + dfs(new_mask)
                            max_score = max(max_score, score)
            return max_score
        
        return dfs(0)

Implementation Explanation: We first precompute all pairwise GCDs for efficiency. The recursive function dfs uses a bitmask to represent used elements. For each state, it tries all unused pairs, calculates the score for the current operation, and recursively evaluates the remaining elements. Memoization via lru_cache ensures that each mask is computed only once.

Go Solution

package main

import (
    "math/bits"
)

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

func maxScore(nums []int) int {
    n := len(nums) / 2
    pairGCD := make([][]int, 2*n)
    for i := range pairGCD {
        pairGCD[i] = make([]int, 2*n)
    }
    for i := 0; i < 2*n; i++ {
        for j := i + 1; j < 2*n; j++ {
            pairGCD[i][j] = gcd(nums[i], nums[j])
        }
    }

    memo := make(map[int]int)

    var dfs func(mask int) int
    dfs = func(mask int) int {
        if val, ok := memo[mask]; ok {
            return val
        }
        usedCount := bits.OnesCount(uint(mask))
        if usedCount == 2*n {
            return 0
        }
        opIndex := usedCount/2 + 1
        maxScore := 0
        for i := 0; i < 2*n; i++ {
            if mask&(1<<i) == 0 {
                for j := i + 1; j < 2*n; j++ {
                    if mask&(1<<j) == 0 {
                        newMask := mask | (1 << i) | (1 << j)
                        score := opIndex*pairGCD[i][j] + dfs(newMask)
                        if score > maxScore {
                            maxScore = score
                        }
                    }
                }
            }
        }
        memo[mask] = maxScore
        return maxScore
    }

    return dfs(0)
}

Go Implementation Notes: The Go solution mirrors the Python logic. We use bits.OnesCount to count used elements and a map[int]int for memoization since Go lacks native function decorators like lru_cache. Precomputing GCDs avoids repeated computation.

Worked Examples

Example 1: nums = [1,2]

  • Initial mask = 0
  • Only one operation possible: pair (1,2), op_index = 1, score = 1 * gcd(1,2) = 1
  • Return 1

Example 2: nums = [3,4,6,8]

Step Mask (binary) Used Count Operation Index Pair Score Total
1 0000 0 1 (3,6) 3 3 + dfs(1010)
2 1010 2 2 (4,8) 8 3+8=11

Final maximum score = 11

Example 3: nums = [1,2,3,4,5,6]

  • Optimal pairings: (1,5), (2,4), (3,6)
  • Scores: 1_1 + 2_2 + 3*3 = 1 + 4 + 9 = 14

Complexity Analysis

Measure Complexity Explanation
Time O(4^n * n^2) Each state has up to C(2n, 2) pairs to explore; memoization reduces duplicate computations.
Space O(2^(2n)) Memoization storage for each possible mask.

The bitmask DP ensures that all states are evaluated efficiently. Precomputing GCDs reduces repeated calculations in recursion.

Test Cases

# Provided examples
assert Solution().maxScore([1,2]) == 1  # smallest case
assert Solution().maxScore([3