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.

Description Hints 2 Solution Video 18:20

1799. Maximize Score After N Operations

Hard57.8% acceptance2 companies

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⁶

Asked at 2 companies

Groww Sprinklr

Topics

Hints open one at a time

Hint 1

Find every way to split the array until n groups of 2. Brute force recursion is acceptable.

Hint 2

Calculate the gcd of every pair and greedily multiply the largest gcds.

18:20

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxScore(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,2]

Input

[3,4,6,8]

Input

[1,2,3,4,5,6]

Your code is saved on this device.Solution