1799. Maximize Score after N Operations - Explanation

1. Brute Force (Backtracking)

Intuition

We need to perform exactly n operations on an array of 2n elements, where each operation picks two elements, computes their GCD, and multiplies it by the operation number. Since we want to maximize the total score, we should try all possible ways to pair up elements and track the best result.

The backtracking approach explores every possible pairing. At each step, we pick any two unvisited elements, mark them as used, compute the score for this operation, then recursively solve for the remaining elements. After exploring that path, we backtrack by unmarking those elements and trying different pairs.

Algorithm

Create a visit array to track which elements have been used.
Define a recursive dfs(n) function where n is the current operation number (starting from 1).
Base case: if n > N/2, all operations are done, return 0.
For each pair of unvisited indices (i, j):
- Mark both as visited.
- Compute n * gcd(nums[i], nums[j]) plus the recursive result for the next operation.
- Track the maximum score.
- Backtrack by unmarking both indices.
Return the maximum score found.

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        N = len(nums)
        visit = [False] * N

        def dfs(n):
            if n > (N // 2):
                return 0

            res = 0
            for i in range(N):
                if visit[i]:
                    continue
                visit[i] = True
                for j in range(i + 1, N):
                    if visit[j]:
                        continue
                    visit[j] = True
                    g = gcd(nums[i], nums[j])
                    res = max(res, n * g + dfs(n + 1))
                    visit[j] = False
                visit[i] = False

            return res

        return dfs(1)

Time & Space Complexity

Time complexity: $O(n ^ n * \log m)$
Space complexity: $O(n)$

Where $n$ is the size of the array $nums$ and $m$ is the maximum element in the array.

2. Bitmask DP (Top-Down) - I

Intuition

The brute force approach has redundant computation because the same subset of remaining elements can be reached through different pairing sequences. We can optimize by caching results based on which elements have been used.

A bitmask elegantly represents which elements are taken. Each bit position corresponds to an array index: bit i being 1 means nums[i] is used. Since the operation number can be derived from counting set bits (every 2 used elements means one completed operation), the mask alone uniquely defines the state.

Algorithm

Use a hash map cache to store the maximum score achievable from each bitmask state.
Define dfs(mask, op) where mask tracks used elements and op is the current operation number.
If mask is already cached, return the stored value.
For each pair of indices (i, j) where neither bit is set:
- Create newMask by setting bits i and j.
- Compute op * gcd(nums[i], nums[j]) plus recursive result.
- Update the maximum score for this mask.
Cache and return the result.

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        cache = collections.defaultdict(int)

        def dfs(mask, op):
            if mask in cache:
                return cache[mask]

            for i in range(len(nums)):
                for j in range(i + 1, len(nums)):
                    if (1 << i) & mask or (1 << j) & mask:
                        continue

                    newMask = mask | (1 << i) | (1 << j)
                    score = op * math.gcd(nums[i], nums[j])
                    cache[mask] = max(
                        cache[mask],
                        score + dfs(newMask, op + 1)
                    )

            return cache[mask]

        return dfs(0, 1)

Time & Space Complexity

Time complexity: $O(n ^ 2 * 2 ^ n * \log m)$
Space complexity: $O(2 ^ n)$

Where $n$ is the size of the array $nums$ and $m$ is the maximum element in the array.

3. Bitmask DP (Top-Down) - II

Intuition

We can further optimize by precomputing all pairwise GCD values. In the previous approach, we recompute gcd(nums[i], nums[j]) every time we consider that pair. Since the same pair appears in many different states, precomputing these values into a 2D table saves repeated GCD calculations.

Additionally, using an array instead of a hash map for memoization provides faster access since bitmask states are contiguous integers from 0 to 2^n - 1.

Algorithm

Precompute a GCD[i][j] table storing gcd(nums[i], nums[j]) for all pairs where i < j.
Create a dp array of size 2^n initialized to -1 (unvisited).
Define dfs(mask, op) similar to before, but look up GCD values from the precomputed table.
Use the dp array for memoization instead of a hash map.
Return dfs(0, 1) as the answer.

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        n = len(nums)
        GCD = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(i + 1, n):
                GCD[i][j] = gcd(nums[i], nums[j])

        dp = [-1] * (1 << n)
        def dfs(mask, op):
            if dp[mask] != -1:
                return dp[mask]

            max_score = 0
            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)
                    max_score = max(
                        max_score,
                        op * GCD[i][j] + dfs(new_mask, op + 1)
                    )

            dp[mask] = max_score
            return max_score

        return dfs(0, 1)

Time & Space Complexity

Time complexity: $O(n ^ 2 * (2 ^ n + \log m))$
Space complexity: $O(n ^ 2 + 2 ^ n)$

Where $n$ is the size of the array $nums$ and $m$ is the maximum element in the array.

4. Bitmask DP (Bottom-Up)

Intuition

Instead of recursion with memoization, we can fill the DP table iteratively. The key observation is that a state with more bits set depends on states with fewer bits set. By iterating from higher masks (more elements used) to lower masks (fewer elements used), we ensure that when we process a state, all states it transitions to are already computed.

The operation number for a given mask is determined by counting how many bits are set and dividing by 2, then adding 1 for the next operation.

Algorithm

Precompute the GCD[i][j] table for all pairs.
Create a dp array of size 2^n initialized to 0.
Iterate mask from 2^n - 1 down to 0:
- Count the number of set bits. Skip if it is odd (invalid state).
- Calculate op = bits / 2 + 1 (the next operation number).
- For each pair (i, j) not in the current mask:
  - Compute new_mask = mask | (1 << i) | (1 << j).
  - Update dp[mask] = max(dp[mask], op * GCD[i][j] + dp[new_mask]).
Return dp[0].

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        n = len(nums)
        N = 1 << n
        GCD = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(i + 1, n):
                GCD[i][j] = gcd(nums[i], nums[j])

        dp = [0] * N
        for mask in range(N - 1, -1, -1):
            bits = bin(mask).count('1')
            if bits % 2 == 1:
                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)
                    dp[mask] = max(dp[mask], op * GCD[i][j] + dp[new_mask])

        return dp[0]

Time & Space Complexity

Time complexity: $O(n ^ 2 * (2 ^ n + \log m))$
Space complexity: $O(n ^ 2 + 2 ^ n)$

Where $n$ is the size of the array $nums$ and $m$ is the maximum element in the array.

Common Pitfalls

Forgetting to Multiply by Operation Number

Each operation's score is i * gcd(nums[a], nums[b]) where i is the operation number (1-indexed). Forgetting the multiplier or using 0-indexed operation numbers produces incorrect scores.

Using Wrong Bit Count for Operation Number

In bitmask DP, the operation number is derived from the number of set bits divided by 2, plus 1 (since each operation uses 2 elements). Off-by-one errors in this calculation cascade through all subsequent operations.

Not Precomputing GCD Values

Recomputing gcd(nums[i], nums[j]) inside the DP loop for every state transition leads to TLE on larger inputs. Precomputing all pairwise GCD values into a 2D table provides significant speedup.

Skipping Invalid Bitmask States

In bottom-up DP, states with an odd number of set bits are invalid (you cannot pair up an odd number of elements). Failing to skip these states wastes computation and can cause incorrect transitions.

Incorrect Bitmask Transition

When marking elements as used, the new mask should be mask | (1 << i) | (1 << j). Using XOR or other operations instead of OR can incorrectly toggle bits that are already set, corrupting the state.