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:
x and y.i * gcd(x, y).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 <= 7nums.length == 2 * n1 <= nums[i] <= 106#1799 Maximize Score After N Operations requires selecting pairs of numbers over multiple operations to maximize the total score. Each operation multiplies its index with the gcd of the chosen pair, so the challenge is deciding the optimal pairing order.
A powerful strategy is to use bitmask dynamic programming. Since the array size is small (2n elements), we can represent which elements are already used with a bitmask. For every mask, we try forming a pair from unused elements and compute the contribution based on the current operation number. Precomputing gcd values for all pairs helps reduce repeated calculations.
The DP state stores the best score achievable for a given mask of used elements. By exploring all valid pairings with memoization, we avoid redundant work while ensuring the optimal score is found. This approach efficiently navigates the exponential pairing possibilities using caching and bit manipulation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bitmask Dynamic Programming with GCD Precomputation | O(n^2 * 2^(2n)) | O(2^(2n) + n^2) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Find every way to split the array until n groups of 2. Brute force recursion is acceptable.
Calculate the gcd of every pair and greedily multiply the largest gcds.
This approach uses backtracking to explore all possible pairs of elements for the operations. The goal is to maximize the sum of scores obtained from each operation. To optimize the solution, pruning is applied by avoiding redundant calculations using a memoization table. By systematically trying all combinations, we gradually eliminate suboptimal solutions and select the maximal score possible.
Time Complexity: O((2n)! / 2^n), the approach explores all possible combinations of pairs.
Space Complexity: O(2^n), for memoization array to store intermediate results.
1using System;
2
3public class MaxScore {
4 static int GCD(int a, int b) {
5 while (b != 0) {
6 int temp = b;
7 b = a % b;
8 a = temp;
9 }
10 return a;
11 }
12
13 static void Backtrack(int[] nums, int n, int used, int currentScore, ref int maxScore, int[] memo) {
14 if (used == (1 << n) - 1) {
maxScore = Math.Max(maxScore, currentScore);
return;
}
if (memo[used] >= currentScore) {
return;
}
memo[used] = currentScore;
for (int i = 0; i < n; ++i) {
if ((used & (1 << i)) == 0) {
for (int j = i + 1; j < n; ++j) {
if ((used & (1 << j)) == 0) {
int pairScore = GCD(nums[i], nums[j]) * ((BitCount(used) / 2) + 1);
Backtrack(nums, n, used | (1 << i) | (1 << j), currentScore + pairScore, ref maxScore, memo);
}
}
}
}
}
static int BitCount(int number) {
int count = 0;
while (number != 0) {
count += number & 1;
number >>= 1;
}
return count;
}
public static int MaxScore(int[] nums) {
int n = nums.Length / 2;
int maxScore = 0;
int[] memo = new int[1 << nums.Length];
Backtrack(nums, n, 0, 0, ref maxScore, memo);
return maxScore;
}
public static void Main() {
int[] nums = {1, 2, 3, 4, 5, 6};
Console.WriteLine("Max Score: " + MaxScore(nums));
}
}The C# solution uses recursive backtracking with bit manipulation. Memoization is leveraged through internal array tracking.
This approach leverages dynamic programming along with bit masking to compute the maximum score possible. The idea is to use a DP state to remember the best score possible with a certain combination of pairs already taken. The state is determined by a bitmask which indicates the taken pairs. Recursively calculate the maximum possible score, storing intermediate results to avoid repeated calculations.
Time Complexity: O(n^2 * 2^n), where n is the number of elements in 'nums'.
Space Complexity: O(2^n) for the DP array.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Bitmasking efficiently tracks which elements in the array have already been paired. Since the array size is small, representing used elements as bits allows fast state transitions and memoization in the dynamic programming solution.
The score for each operation depends on the GCD of the chosen pair multiplied by the operation index. Precomputing GCD values for all pairs helps avoid repeated calculations and speeds up the DP transitions.
Yes, this problem is considered a challenging interview question because it combines bitmask DP, number theory, and combinatorial pairing. Variants of this problem can appear in advanced technical interviews at top tech companies.
The optimal approach uses bitmask dynamic programming combined with precomputed GCD values. Each bitmask represents which elements are already used, and the DP explores valid pairings to maximize the score across operations.
The solution maintains a DP array where each entry dp[mask] stores the maximum score achievable for a set of already chosen pairs defined by 'mask'. The nested loops iterate over possible pairings, dynamically updating the DP array.