# Maximize Score After N Operations
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximize-score-after-n-operations)
Canonical: https://scaleengineer.com/dsa/problems/maximize-score-after-n-operations
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
**Companies:** [Sprinklr](https://scaleengineer.com/companies/sprinklr)
---
## Problem
You are given `nums`, an array of positive integers of size `2 * n`. You must perform `n` operations on this array.

In the `ith` operation **(1-indexed)**, you will:

* Choose two elements, `x` and `y`.
* Receive a score of `i * gcd(x, y)`.
* Remove `x` and `y` from `nums`.

Return _the maximum score you can receive after performing_ `n` _operations._

The function `gcd(x, y)` is the greatest common divisor of `x` and `y`.

**Example 1:**

**Input:** nums = [1,2]
**Output:** 1
**Explanation:** The optimal choice of operations is:
(1 * gcd(1, 2)) = 1

**Example 2:**

**Input:** nums = [3,4,6,8]
**Output:** 11
**Explanation:** The optimal choice of operations is:
(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11

**Example 3:**

**Input:** nums = [1,2,3,4,5,6]
**Output:** 14
**Explanation:** The optimal choice of operations is:
(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14

**Constraints:**

* `1 <= n <= 7`
* `nums.length == 2 * n`
* `1 <= nums[i] <= 106`

# Approaches
## Brute-Force Backtracking
This approach involves exploring every possible sequence of pairs that can be formed from the input array. It uses a recursive backtracking method to generate all valid combinations of `n` pairs, calculates the score for each complete sequence of operations, and keeps track of the maximum score found.
**Time:** O(n * (2n)! / (2^n * n!)). The recursion tree is very wide. At each of the `n` levels of recursion, we choose a pair from the remaining numbers. The number of ways to partition `2n` elements into `n` pairs is `(2n)! / (n! * 2^n)`. Since the order of pairs matters, we explore many permutations. This complexity is too high for the given constraints. · **Space:** O(n), for the recursion stack depth. The space for the mask and other variables is constant per call.
**Pros:** Conceptually simple and a direct translation of the problem statement.; Guaranteed to find the correct answer as it explores the entire search space.
**Cons:** Extremely inefficient due to a very large number of redundant computations. The same subproblem (finding the max score for a given subset of remaining numbers) is solved multiple times.; The time complexity is prohibitive and will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
### Explanation
The brute-force strategy is implemented with a recursive helper function that systematically tries every choice at each step. The state of the recursion is defined by the current operation number (`op`), the score accumulated so far (`currentScore`), and a bitmask (`mask`) to keep track of which numbers have been used.

In the `op`-th step, the function iterates through all available numbers, forms a pair `(x, y)`, adds `op * gcd(x, y)` to the score, and then recursively calls itself for the `(op+1)`-th step with the updated state. The recursion bottoms out after `n` operations have been simulated. A global variable is maintained to store the maximum score encountered across all the explored paths.

```java
class Solution {
    int maxScoreVal = 0;
    int[] Nums;
    int N;

    public int maxScore(int[] nums) {
        this.Nums = nums;
        this.N = nums.length;
        backtrack(1, 0, 0);
        return maxScoreVal;
    }

    private void backtrack(int op, int currentScore, int mask) {
        if (op > N / 2) {
            maxScoreVal = Math.max(maxScoreVal, currentScore);
            return;
        }

        for (int i = 0; i < N; i++) {
            if ((mask & (1 << i)) != 0) continue;
            for (int j = i + 1; j < N; j++) {
                if ((mask & (1 << j)) != 0) continue;
                
                int newMask = mask | (1 << i) | (1 << j);
                int scoreToAdd = op * gcd(Nums[i], Nums[j]);
                backtrack(op + 1, currentScore + scoreToAdd, newMask);
            }
        }
    }
    
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### Algorithm
- Create a recursive function `backtrack(op, currentScore, mask)`.
- `op`: The current operation number, from 1 to `n`.
- `currentScore`: The score accumulated so far.
- `mask`: A bitmask representing the indices of numbers that have already been used.
- **Base Case**: If `op` is greater than `n`, it means `n` operations have been completed. We compare `currentScore` with a global maximum and update it if `currentScore` is larger.
- **Recursive Step**: Iterate through all possible pairs of unused numbers `(nums[i], nums[j])`. To find unused numbers, check if the `i`-th and `j`-th bits are unset in the `mask`.
- For each valid pair, calculate the score for the current operation: `op * gcd(nums[i], nums[j])`.
- Make a recursive call for the next operation: `backtrack(op + 1, currentScore + newScore, newMask)`, where `newMask` is the old `mask` with bits for `i` and `j` set.
- The initial call to start the process is `backtrack(1, 0, 0)`.

## Dynamic Programming with Bitmasking
This approach significantly optimizes the brute-force solution by using dynamic programming with memoization. The state of a subproblem is defined by the subset of numbers that have already been used. A bitmask is a perfect way to represent this subset. By storing the result for each mask, we avoid re-computing the answer for the same subproblem, drastically reducing the overall computation time.
**Time:** O(2^(2n) * (2n)^2). There are `2^(2n)` possible states (masks). For each state, we iterate through all possible pairs of available numbers, which is at most `O((2n)^2)`. The `gcd` calculation adds a logarithmic factor, making it `O(2^(2n) * (2n)^2 * log(A))`, where `A` is the maximum value in `nums`. · **Space:** O(2^(2n)). The dominant factor is the memoization table, which needs to store a result for each possible bitmask. The recursion stack depth adds `O(n)`, which is negligible.
**Pros:** Guarantees the optimal solution.; Efficient enough to pass within the time limits for the given constraints (`n <= 7`).; It's a standard and powerful technique for problems with small constraints involving subsets or permutations.
**Cons:** The space complexity is exponential, `O(2^(2n))`, which limits the feasibility of this approach to small values of `n` (up to around 10-12).
### Explanation
The key insight is that the maximum score achievable from a set of remaining numbers is independent of how the previous pairs were formed, only depending on which numbers are left and which operation number is next. We can define a function, `solve(mask)`, that computes the maximum score for the numbers not yet taken, represented by the `mask`.

The number of operations already performed can be deduced from the number of set bits in the mask. If `k` bits are set, `k/2` pairs have been chosen, and we are at operation `k/2 + 1`.

We use a `memo` array to store the results of `solve(mask)`. When `solve(mask)` is called, it first checks if the result is already in `memo`. If so, it returns it immediately. Otherwise, it computes the result by trying all possible pairs from the available numbers, making recursive calls for the next state, and storing the best result in `memo` before returning.

```java
class Solution {
    int[] memo;
    int[] Nums;
    int N; // This will be 2*n

    public int maxScore(int[] nums) {
        this.Nums = nums;
        this.N = nums.length;
        this.memo = new int[1 << N];
        return solve(0);
    }

    private int solve(int mask) {
        if (mask == (1 << N) - 1) {
            return 0; // All numbers have been used
        }
        if (memo[mask] != 0) {
            return memo[mask];
        }

        int usedCount = Integer.bitCount(mask);
        int op = usedCount / 2 + 1;
        int maxVal = 0;

        for (int i = 0; i < N; i++) {
            if ((mask & (1 << i)) != 0) continue;
            for (int j = i + 1; j < N; j++) {
                if ((mask & (1 << j)) != 0) continue;
                
                int newMask = mask | (1 << i) | (1 << j);
                int currentScore = op * gcd(Nums[i], Nums[j]) + solve(newMask);
                maxVal = Math.max(maxVal, currentScore);
            }
        }

        memo[mask] = maxVal;
        return maxVal;
    }
    
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### Algorithm
- Create a memoization array `memo` of size `2^(2*n)` and initialize it with a value indicating that states are not yet computed (e.g., 0, since scores are positive).
- Define a recursive function `solve(mask)` which calculates the maximum score from the set of numbers not yet used (as indicated by the `mask`).
- **Base Case**: If `mask` has all bits set to 1, it means all numbers have been used. Return 0.
- **Memoization Check**: If `memo[mask]` has been computed, return the stored value.
- **Recursive Step**:
  - Determine the current operation number. This can be calculated from the number of set bits in the `mask`: `op = (Integer.bitCount(mask) / 2) + 1`.
  - Initialize a variable `maxVal` to 0 to track the maximum score for the current state.
  - Iterate through all pairs of indices `(i, j)` corresponding to numbers not yet used (i.e., `i`-th and `j`-th bits are 0 in `mask`).
  - For each pair, calculate the score for this choice and add the result of the recursive call for the subsequent state: `currentScore = op * gcd(nums[i], nums[j]) + solve(newMask)`, where `newMask` is `mask | (1 << i) | (1 << j)`.
  - Update `maxVal = Math.max(maxVal, currentScore)`.
- Store the result `maxVal` in `memo[mask]` before returning it.
- The final answer is the result of the initial call `solve(0)`.

# Solutions
### Java

```java
class Solution {
public
  int maxScore(int[] nums) {
    int m = nums.length;
    int[][] g = new int[m][m];
    for (int i = 0; i < m; ++i) {
      for (int j = i + 1; j < m; ++j) {
        g[i][j] = gcd(nums[i], nums[j]);
      }
    }
    int[] f = new int[1 << m];
    for (int k = 0; k < 1 << m; ++k) {
      int cnt = Integer.bitCount(k);
      if (cnt % 2 == 0) {
        for (int i = 0; i < m; ++i) {
          if (((k >> i) & 1) == 1) {
            for (int j = i + 1; j < m; ++j) {
              if (((k >> j) & 1) == 1) {
                f[k] = Math.max(f[k],
                                f[k ^ (1 << i) ^ (1 << j)] + cnt / 2 * g[i][j]);
              }
            }
          }
        }
      }
    }
    return f[(1 << m) - 1];
  }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

```

### CPP

```cpp
class Solution {
public:
  int maxScore(vector<int> &nums) {
    int m = nums.size();
    int g[m][m];
    for (int i = 0; i < m; ++i) {
      for (int j = i + 1; j < m; ++j) {
        g[i][j] = gcd(nums[i], nums[j]);
      }
    }
    int f[1 << m];
    memset(f, 0, sizeof f);
    for (int k = 0; k < 1 << m; ++k) {
      int cnt = __builtin_popcount(k);
      if (cnt % 2 == 0) {
        for (int i = 0; i < m; ++i) {
          if (k >> i & 1) {
            for (int j = i + 1; j < m; ++j) {
              if (k >> j & 1) {
                f[k] =
                    max(f[k], f[k ^ (1 << i) ^ (1 << j)] + cnt / 2 * g[i][j]);
              }
            }
          }
        }
      }
    }
    return f[(1 << m) - 1];
  }
};

```

### Python

```python
class Solution:
    def maxScore(self, nums: List[int]) -> int: m = len(nums) f = [0] * (1 << m) g = [[0] * m for _ in range(m)] for i in range(m): for j in range(i + 1, m): g[i][j] = gcd(nums[i], nums[j]) for k in range(1 << m): if (cnt: = k . bit_count()) % 2 == 0: for i in range(m): if k >> i & 1: for j in range(i + 1, m): if k >> j & 1: f[k] = max(f[k], f[k ^ (1 << i) ^ (1 << j)] + cnt // 2 * g[i][j], ) return f[- 1]

```