Maximize Score After N Operations

Challenge Points: 30

Level: Hard

You are given an array nums containing 2 * n positive integers.
You must perform exactly n operations, where each operation removes two numbers from the array.

During the i-th operation (1-indexed):

Select two values x and y from the array.
Earn i * gcd(x, y) points.
Remove x and y from the array.

Your goal is to determine the maximum total score that can be achieved after completing all n operations.

Example 1:

Input: nums = [2, 3, 4, 9]

Output: 8

Explanation:

(1 * gcd(3, 9)) + (2 * gcd(2, 4)) = 3 + 8 = 11 (but maybe a different pairing gives 10 depending on strategy)

Example 2:

Input: nums = [2, 6]

Output: 3

Explanation:

Only one operation possible: 1 * gcd(2, 6) = 2

Example 3:

Input: nums = [5, 10, 15, 20]

Output: 25

Explanation:

Explanation: (1 * gcd(5, 15)) + (2 * gcd(10, 20)) = 5 + 12 = 17

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result