Skip to main content
Talentd

Maximize Score After N Operations - Solution & Explanation

HardArrayMathDynamic ProgrammingBacktracking22 min readAsked at: Sprinklr, Groww
Practice this problem

Problem Statement

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

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.

Backtracking in C

This C implementation uses bit manipulation to keep track of used numbers and compute GCD pairs selectively. The recursive function 'backtrack' explores all pairs of elements, marking them as used and calculating their scores. The result is updated if a higher score is found. Memoization is added to store intermediate results to prevent recalculations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

Dynamic Programming in C

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Backtracking with Pruning

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.

Approach 2: Dynamic Programming with Bitmask

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.

State Compression + Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with PruningO((2n)! / (2^n · n!))O(n)When demonstrating the brute-force pairing logic or when constraints are very small
Dynamic Programming with BitmaskO(m² · 2^m)O(2^m)General optimal solution for subset pairing problems with m ≤ 14 elements

Video Solution

Maximize Score after N Operations - Leetcode 1799 - Python • NeetCodeIO • 10,018 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximize Score After N Operations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays