Maximize Score After N Operations

Hard

#1645Time: 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.1 company

Patterns

Math Dynamic Programming Backtracking Bit Manipulation Number Theory Bitmask

Data structures

Array

Companies

Sprinklr

Prompt

You are given nums, an array of positive integers of size 2 * n. You must perform n operations on this array.

In the i^th 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] <= 10⁶

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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).

Walkthrough

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.

1class Solution {2    int maxScoreVal = 0;3    int[] Nums;4    int N;5 6    public int maxScore(int[] nums) {7        this.Nums = nums;8        this.N = nums.length;9        backtrack(1, 0, 0);10        return maxScoreVal;11    }12 13    private void backtrack(int op, int currentScore, int mask) {14        if (op > N / 2) {15            maxScoreVal = Math.max(maxScoreVal, currentScore);16            return;17        }18 19        for (int i = 0; i < N; i++) {20            if ((mask & (1 << i)) != 0) continue;21            for (int j = i + 1; j < N; j++) {22                if ((mask & (1 << j)) != 0) continue;23                24                int newMask = mask | (1 << i) | (1 << j);25                int scoreToAdd = op * gcd(Nums[i], Nums[j]);26                backtrack(op + 1, currentScore + scoreToAdd, newMask);27            }28        }29    }30    31    private int gcd(int a, int b) {32        while (b != 0) {33            int temp = b;34            b = a % b;35            a = temp;36        }37        return a;38    }39}

Complexity

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.

Trade-offs

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.

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.

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).

Walkthrough

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.

1class Solution {2    int[] memo;3    int[] Nums;4    int N; // This will be 2*n5 6    public int maxScore(int[] nums) {7        this.Nums = nums;8        this.N = nums.length;9        this.memo = new int[1 << N];10        return solve(0);11    }12 13    private int solve(int mask) {14        if (mask == (1 << N) - 1) {15            return 0; // All numbers have been used16        }17        if (memo[mask] != 0) {18            return memo[mask];19        }20 21        int usedCount = Integer.bitCount(mask);22        int op = usedCount / 2 + 1;23        int maxVal = 0;24 25        for (int i = 0; i < N; i++) {26            if ((mask & (1 << i)) != 0) continue;27            for (int j = i + 1; j < N; j++) {28                if ((mask & (1 << j)) != 0) continue;29                30                int newMask = mask | (1 << i) | (1 << j);31                int currentScore = op * gcd(Nums[i], Nums[j]) + solve(newMask);32                maxVal = Math.max(maxVal, currentScore);33            }34        }35 36        memo[mask] = maxVal;37        return maxVal;38    }39    40    private int gcd(int a, int b) {41        while (b != 0) {42            int temp = b;43            b = a % b;44            a = temp;45        }46        return a;47    }48}

Complexity

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.

Trade-offs

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).

Solutions

Solution

1class Solution {2public3  int maxScore(int[] nums) {4    int m = nums.length;5    int[][] g = new int[m][m];6    for (int i = 0; i < m; ++i) {7      for (int j = i + 1; j < m; ++j) {8        g[i][j] = gcd(nums[i], nums[j]);9      }10    }11    int[] f = new int[1 << m];12    for (int k = 0; k < 1 << m; ++k) {13      int cnt = Integer.bitCount(k);14      if (cnt % 2 == 0) {15        for (int i = 0; i < m; ++i) {16          if (((k >> i) & 1) == 1) {17            for (int j = i + 1; j < m; ++j) {18              if (((k >> j) & 1) == 1) {19                f[k] = Math.max(f[k],20                                f[k ^ (1 << i) ^ (1 << j)] + cnt / 2 * g[i][j]);21              }22            }23          }24        }25      }26    }27    return f[(1 << m) - 1];28  }29private30  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }31}

1class Solution {2public:3  int maxScore(vector<int> &nums) {4    int m = nums.size();5    int g[m][m];6    for (int i = 0; i < m; ++i) {7      for (int j = i + 1; j < m; ++j) {8        g[i][j] = gcd(nums[i], nums[j]);9      }10    }11    int f[1 << m];12    memset(f, 0, sizeof f);13    for (int k = 0; k < 1 << m; ++k) {14      int cnt = __builtin_popcount(k);15      if (cnt % 2 == 0) {16        for (int i = 0; i < m; ++i) {17          if (k >> i & 1) {18            for (int j = i + 1; j < m; ++j) {19              if (k >> j & 1) {20                f[k] =21                    max(f[k], f[k ^ (1 << i) ^ (1 << j)] + cnt / 2 * g[i][j]);22              }23            }24          }25        }26      }27    }28    return f[(1 << m) - 1];29  }30};

1class Solution:2    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]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem