Maximize Score After N Operations solution and explanation
9 more videos on this problem
Maximize Score after N Operations - Leetcode 1799 - PythonNeetCodeIO · 18:20 · 10K views
Maximize Score After N Operations | BRUTE FORCE To OPTIMAL | META | Leetcode-1799 | Live CodecodestorywithMIK · 41:34 · 7K views
Maximize Score After N Operations of Leetcode || DP with Bitmasking || C++/Java/Python || DPAryan Mittal · 37:41 · 7K views
LeetCode 1799. Maximize Score After N OperationsHappy Coding · 10:35 · 6K views
花花酱 LeetCode 1799. Maximize Score After N Operations - 刷题找工作 EP390Hua Hua · 14:57 · 2K views
LeetCode 1799. Maximize Score After N Operations (Hard) | Dynamic Programming | C++Ascorbichelix · 12:32 · 2K views
1799. Maximize Score After N Operations (Leetcode Hard)Programming Live with Larry · 20:59 · 2K views
1799. Maximize Score After N Operations | DP with Bit Masking | LeetCode Daily Challenge POTDDeep Tech · 21:19 · 1K views
LeetCode 1799. [HARD] Maximize Score After N OperationsFrancesco Manicardi · 7:48 · 1K views
DP session (Leetcode Hard problem) - 1799. Maximize Score After N OperationsCoding BeTounsi · 46:01 · 1K views
The 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,
xandy. - Receive a score of
i * gcd(x, y). - Remove
xandyfromnums.
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
Approach overview
Problem Overview: You are given 2n integers. In each operation, pick two unused numbers, compute their gcd, and add operation_index × gcd to the score. After n operations all numbers are used. The goal is to choose pairings that maximize the total score.
Approach 1: Backtracking with Pruning (Time: O((2n)! / (2^n · n!)), Space: O(n))
This approach tries every possible way to form pairs. At each step you iterate through unused numbers, pick two, compute their gcd, and recursively continue with the remaining elements. The operation number increases each time, so earlier choices influence the final score significantly. Pruning helps slightly: skip already-used indices and avoid recomputing states where the same numbers remain. The algorithm essentially enumerates all pair combinations, which grows quickly but still works because 2n ≤ 14. The method directly demonstrates the pairing logic and uses recursion with a visited array.
Approach 2: Dynamic Programming with Bitmask (Time: O(m² · 2^m), Space: O(2^m))
The optimized solution represents which numbers are already used with a bitmask of length m = 2n. Each DP state mask stores the maximum score achievable using exactly those elements. Count the number of set bits in the mask to determine the current operation number. For every state, iterate through pairs of unused indices, compute their gcd, and transition to a new mask where both bits are set. Precomputing pairwise gcd values speeds up transitions. This transforms exponential pairing into structured dynamic programming over subsets, a common pattern in bitmask problems. The scoring rule directly leverages number theory through the gcd operation.
Recommended for interviews: Dynamic Programming with Bitmask is the expected solution. Brute-force backtracking shows you understand the pairing structure, but the DP version demonstrates optimization using subset states and avoids recomputing equivalent configurations.
Approach 1: Approach 1: Backtracking with Pruning
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.
from math import gcd
from functools import lru_cache
class Solution:
def maxScore(self, nums):
n = len(nums)
@lru_cache(None)
def backtrack(used):
if used == (1 << n) - 1:
return 0
max_score = 0
for i in range(n):
if not used & (1 << i):
for j in range(i + 1, n):
if not used & (1 << j):
score = gcd(nums[i], nums[j]) * (bin(used).count('1') // 2 + 1)
max_score = max(max_score, score + backtrack(used | (1 << i) | (1 << j)))
return max_score
return backtrack(0)
print(Solution().maxScore([1, 2, 3, 4, 5, 6]))import java.util.*;
public class MaxScore {
static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
static void backtrack(int[] nums, int n, int used, int currentScore, int[] maxScore, int[] memo) {
if (used == (1 << n) - 1) {
maxScore[0] = Math.max(maxScore[0], 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]) * (Integer.bitCount(used) / 2 + 1);
backtrack(nums, n, used | (1 << i) | (1 << j), currentScore + pairScore, maxScore, memo);
}
}
}
}
}
public static int maxScore(int[] nums) {
int n = nums.length / 2;
int[] maxScore = {0};
int[] memo = new int[1 << nums.length];
Arrays.fill(memo, 0);
backtrack(nums, n, 0, 0, maxScore, memo);
return maxScore[0];
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5, 6};
System.out.println("Max Score: " + maxScore(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
void backtrack(vector<int>& nums, int n, int used, int current_score, int& max_score, vector<int>& memo) {
if (used == (1 << n) - 1) {
max_score = max(max_score, current_score);
return;
}
if (memo[used] >= current_score) {
return;
}
memo[used] = current_score;
for (int i = 0; i < n; ++i) {
if (!(used & (1 << i))) {
for (int j = i + 1; j < n; ++j) {
if (!(used & (1 << j))) {
int pairScore = gcd(nums[i], nums[j]) * (__builtin_popcount(used) / 2 + 1);
backtrack(nums, n, used | (1 << i) | (1 << j), current_score + pairScore, max_score, memo);
}
}
}
}
}
int maxScore(vector<int>& nums) {
int max_score = 0;
vector<int> memo(1 << nums.size(), 0);
backtrack(nums, nums.size() / 2, 0, 0, max_score, memo);
return max_score;
}
int main() {
vector<int> nums = {3, 4, 6, 8};
cout << "Max Score: " << maxScore(nums) << endl;
return 0;
}function gcd(a, b) {
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
function backtrack(nums, n, used, currentScore, maxScore, memo) {
if (used === (1 << n) - 1) {
maxScore[0] = Math.max(maxScore[0], currentScore);
return;
}
if (memo[used] >= currentScore) {
return;
}
memo[used] = currentScore;
for (let i = 0; i < n; ++i) {
if (!(used & (1 << i))) {
for (let j = i + 1; j < n; ++j) {
if (!(used & (1 << j))) {
let pairScore = gcd(nums[i], nums[j]) * (bitCount(used) / 2 + 1);
backtrack(nums, n, used | (1 << i) | (1 << j), currentScore + pairScore, maxScore, memo);
}
}
}
}
}
function bitCount(num) {
let count = 0;
while (num !== 0) {
count += num & 1;
num >>= 1;
}
return count;
}
function maxScore(nums) {
const n = nums.length / 2;
let maxScore = [0];
const memo = new Array(1 << nums.length).fill(0);
backtrack(nums, n, 0, 0, maxScore, memo);
return maxScore[0];
}
console.log(maxScore([1, 2, 3, 4, 5, 6]));#include <stdio.h>
#include <stdlib.h>
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
void backtrack(int* nums, int n, int used, int current_score, int* max_score, int* memo) {
if (used == (1 << n) - 1) {
if (current_score > *max_score) {
*max_score = current_score;
}
return;
}
if (memo[used] >= current_score) {
return;
}
memo[used] = current_score;
for (int i = 0; i < n; ++i) {
if (!(used & (1 << i))) {
for (int j = i + 1; j < n; ++j) {
if (!(used & (1 << j))) {
int pairScore = gcd(nums[i], nums[j]) * (__builtin_popcount(used) / 2 + 1);
backtrack(nums, n, used | (1 << i) | (1 << j), current_score + pairScore, max_score, memo);
}
}
}
}
}
int maxScore(int* nums, int numsSize) {
int* memo = (int*)calloc(1 << numsSize, sizeof(int));
int max_score = 0;
backtrack(nums, numsSize / 2, 0, 0, &max_score, memo);
free(memo);
return max_score;
}
int main() {
int nums[] = {1, 2, 3, 4, 5, 6};
int result = maxScore(nums, 6);
printf("Max Score: %d\n", result);
return 0;
}using System;
public class MaxScore {
static int GCD(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
static void Backtrack(int[] nums, int n, int used, int currentScore, ref int maxScore, int[] memo) {
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));
}
}Backtracking in Python
This Python solution uses recursion with LRU caching to store intermediate results and avoid recalculations. The use of bit manipulation effectively tracks used elements and allowed potential score maximization through backtracking.
Time Complexity: O((2n)! / 2^n).
Space Complexity: O(2^n), due to LRU Cache memoization.
Approach 2: Approach 2: Dynamic Programming with Bitmask
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.
from math import gcd
class Solution:
def maxScore(self, nums):
n = len(nums)
dp = [-1] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
ops = bin(mask).count('1') // 2 + 1
for i in range(n):
if not mask & (1 << i):
for j in range(i + 1, n):
if not mask & (1 << j):
new_mask = mask | (1 << i) | (1 << j)
dp[new_mask] = max(dp[new_mask], dp[mask] + ops * gcd(nums[i], nums[j]))
return dp[(1 << n) - 1]
print(Solution().maxScore([3, 4, 6, 8]))import java.util.*;
public class MaxScore {
public static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static int maxScore(int[] nums) {
int n = nums.length / 2;
int[] dp = new int[1 << nums.length];
Arrays.fill(dp, Integer.MIN_VALUE);
dp[0] = 0;
for (int mask = 0; mask < (1 << nums.length); ++mask) {
int ops = Integer.bitCount(mask) / 2 + 1;
for (int i = 0; i < nums.length; ++i) {
if ((mask & (1 << i)) == 0) {
for (int j = i + 1; j < nums.length; ++j) {
if ((mask & (1 << j)) == 0) {
int new_mask = mask | (1 << i) | (1 << j);
dp[new_mask] = Math.max(dp[new_mask], dp[mask] + ops * gcd(nums[i], nums[j]));
}
}
}
}
}
return dp[(1 << nums.length) - 1];
}
public static void main(String[] args) {
int[] nums = {3, 4, 6, 8};
System.out.println("Max Score: " + maxScore(nums));
}
}#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int maxScore(vector<int>& nums) {
int n = nums.size() / 2;
vector<int> dp(1 << nums.size(), INT_MIN);
dp[0] = 0;
for (int mask = 0; mask < (1 << nums.size()); ++mask) {
int ops = __builtin_popcount(mask) / 2 + 1;
for (int i = 0; i < nums.size(); ++i) {
if ((mask & (1 << i)) == 0) {
for (int j = i + 1; j < nums.size(); ++j) {
if ((mask & (1 << j)) == 0) {
int new_mask = mask | (1 << i) | (1 << j);
dp[new_mask] = max(dp[new_mask], dp[mask] + ops * gcd(nums[i], nums[j]));
}
}
}
}
}
return dp[(1 << nums.size()) - 1];
}
int main() {
vector<int> nums = {1, 2, 3, 4, 5, 6};
cout << "Max Score: " << maxScore(nums) << endl;
return 0;
}function gcd(a, b) {
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
function maxScore(nums) {
const n = nums.length / 2;
const dp = new Array(1 << nums.length).fill(Number.NEGATIVE_INFINITY);
dp[0] = 0;
for (let mask = 0; mask < (1 << nums.length); ++mask) {
const ops = bitCount(mask) / 2 + 1;
for (let i = 0; i < nums.length; ++i) {
if (!(mask & (1 << i))) {
for (let j = i + 1; j < nums.length; ++j) {
if (!(mask & (1 << j))) {
const new_mask = mask | (1 << i) | (1 << j);
dp[new_mask] = Math.max(dp[new_mask], dp[mask] + ops * gcd(nums[i], nums[j]));
}
}
}
}
}
return dp[(1 << nums.length) - 1];
}
function bitCount(num) {
let count = 0;
while (num !== 0) {
count += num & 1;
num >>= 1;
}
return count;
}
console.log(maxScore([3, 4, 6, 8]));#include <stdio.h>
#include <math.h>
#include <limits.h>
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int maxScore(int* nums, int numsSize) {
int n = numsSize / 2;
int dp[1 << numsSize];
for (int i = 0; i < (1 << numsSize); ++i) dp[i] = -1;
dp[0] = 0;
for (int mask = 0; mask < (1 << numsSize); ++mask) {
int ops = __builtin_popcount(mask) / 2 + 1;
for (int i = 0; i < numsSize; ++i) {
if (!(mask & (1 << i))) {
for (int j = i + 1; j < numsSize; ++j) {
if (!(mask & (1 << j))) {
int new_mask = mask | (1 << i) | (1 << j);
dp[new_mask] = fmax(dp[new_mask], dp[mask] + ops * gcd(nums[i], nums[j]));
}
}
}
}
}
return dp[(1 << numsSize) - 1];
}
int main() {
int nums[] = {3, 4, 6, 8};
printf("Max Score: %d\n", maxScore(nums, 4));
return 0;
}using System;
public class MaxScore {
public static int GCD(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static int MaxScore(int[] nums) {
int n = nums.Length / 2;
int[] dp = new int[1 << nums.Length];
Array.Fill(dp, int.MinValue);
dp[0] = 0;
for (int mask = 0; mask < (1 << nums.Length); ++mask) {
int ops = BitCount(mask) / 2 + 1;
for (int i = 0; i < nums.Length; ++i) {
if ((mask & (1 << i)) == 0) {
for (int j = i + 1; j < nums.Length; ++j) {
if ((mask & (1 << j)) == 0) {
int new_mask = mask | (1 << i) | (1 << j);
dp[new_mask] = Math.Max(dp[new_mask], dp[mask] + ops * GCD(nums[i], nums[j]));
}
}
}
}
}
return dp[(1 << nums.Length) - 1];
}
public static int BitCount(int n) {
int count = 0;
while (n != 0) {
count += n & 1;
n >>= 1;
}
return count;
}
public static void Main() {
int[] nums = {1, 2, 3, 4, 5, 6};
Console.WriteLine("Max Score: " + MaxScore(nums));
}
}Dynamic Programming in Python
The Python solution performs dynamic programming on a bitmask basis. It iterates over mask states to find and record maximum scores obtained by the best pairings.
Time Complexity: O(n^2 * 2^n).
Space Complexity: O(2^n) due to storage for DP states.
Approach 3: State Compression + Dynamic Programming
We can preprocess to get the greatest common divisor of any two numbers in the array nums, stored in the two-dimensional array g, where g[i][j] represents the greatest common divisor of nums[i] and nums[j].
Then define f[k] to represent the maximum score that can be obtained when the state after the current operation is k. Suppose m is the number of elements in the array nums, then there are a total of 2^m states, that is, the range of k is [0, 2^m - 1].
Enumerate all states from small to large, for each state k, first determine whether the number of 1s in the binary bits of this state cnt is even, if so, perform the following operations:
Enumerate the positions where the binary bits in k are 1, suppose they are i and j, then the elements at positions i and j can perform one operation, and the score that can be obtained at this time is \frac{cnt}{2} times g[i][j], update the maximum value of f[k].
The final answer is f[2^m - 1].
The time complexity is O(2^m times m^2), and the space complexity is O(2^m). Here, m is the number of elements in the array nums.
function maxScore(nums: number[]): number {
const m = nums.length;
const f: number[] = new Array(1 << m).fill(0);
const g: number[][] = new Array(m).fill(0).map(() => new Array(m).fill(0));
for (let i = 0; i < m; ++i) {
for (let j = i + 1; j < m; ++j) {
g[i][j] = gcd(nums[i], nums[j]);
}
}
for (let k = 0; k < 1 << m; ++k) {
const cnt = bitCount(k);
if (cnt % 2 === 0) {
for (let i = 0; i < m; ++i) {
if ((k >> i) & 1) {
for (let j = i + 1; j < m; ++j) {
if ((k >> j) & 1) {
const t = f[k ^ (1 << i) ^ (1 << j)] + ~~(cnt / 2) * g[i][j];
f[k] = Math.max(f[k], t);
}
}
}
}
}
}
return f[(1 << m) - 1];
}
function gcd(a: number, b: number): number {
return b ? gcd(b, a % b) : a;
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}func maxScore(nums []int) int {
m := len(nums)
g := [14][14]int{}
for i := 0; i < m; i++ {
for j := i + 1; j < m; j++ {
g[i][j] = gcd(nums[i], nums[j])
}
}
f := make([]int, 1<<m)
for k := 0; k < 1<<m; k++ {
cnt := bits.OnesCount(uint(k))
if cnt%2 == 0 {
for i := 0; i < m; i++ {
if k>>i&1 == 1 {
for j := i + 1; j < m; j++ {
if k>>j&1 == 1 {
f[k] = max(f[k], f[k^(1<<i)^(1<<j)]+cnt/2*g[i][j])
}
}
}
}
}
}
return f[1<<m-1]
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Backtracking with Pruning | Time Complexity: O((2n)! / 2^n). |
| Approach 2: Dynamic Programming with Bitmask | Time Complexity: O(n^2 * 2^n). |
| State Compression + Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Pruning | O((2n)! / (2^n · n!)) | O(n) | When demonstrating the brute-force pairing logic or when constraints are very small |
| Dynamic Programming with Bitmask | O(m² · 2^m) | O(2^m) | General optimal solution for subset pairing problems with m ≤ 14 elements |
Frequently asked questions
Is Maximize Score After N Operations easy or hard?
Maximize Score After N Operations is classified as Hard on LeetCode. The difficulty comes from recognizing that the pairing problem can be transformed into dynamic programming over subsets using bitmask representation.
Maximize Score After N Operations Python/Java solution
Most implementations use dynamic programming with bitmasking. Precompute gcd values for every pair, iterate over masks, and try pairing unused indices to form the next state. The same algorithm works in Python, Java, C++, and other languages using arrays and bit operations.
How to solve Maximize Score After N Operations in O(n)?
An O(n) solution does not exist for this problem because you must evaluate many pair combinations. The best practical method uses dynamic programming with bitmasking, which runs in O(m² · 2^m). This complexity is manageable because the constraint limits m to at most 14 numbers.
What is the best approach for Maximize Score After N Operations?
Dynamic Programming with Bitmask is the best approach. Each subset of used numbers is represented by a bitmask, and DP stores the maximum score for that state. By iterating through unused pairs and transitioning masks, the algorithm avoids recomputing equivalent states. The total complexity is O(m² · 2^m) where m = 2n.
Is Maximize Score After N Operations asked at Google/Amazon/Meta?
This problem reflects a common interview pattern used by companies like Google, Amazon, and Meta: dynamic programming over subsets with bitmasking. Variants appear in pairing optimization and assignment problems where the state is represented by used elements.
What data structure is used in Maximize Score After N Operations?
The key structure is a DP array indexed by bitmask, where each mask represents which numbers are already used. Additional helpers include a precomputed matrix of gcd values and bit operations to check or set elements in the mask.
What is the time complexity of Maximize Score After N Operations?
The optimized solution runs in O(m² · 2^m) time with O(2^m) space, where m is the number of elements (m = 2n and m ≤ 14). Each DP state represents a subset of used numbers, and transitions try all pairs of unused elements. A brute-force backtracking approach has factorial growth and is significantly slower.