Maximize Score After N Operations - Practice Coding Problems

Maximize Score After N Operations - Problem

Array Math Dynamic Programming Backtracking Bit Manipulation Number Theory Bitmask Hard

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3,4,5,6]

› Output: 14

💡 Note: One optimal sequence: Operation 1: choose (1,5) → 1×gcd(1,5) = 1×1 = 1. Operation 2: choose (2,4) → 2×gcd(2,4) = 2×2 = 4. Operation 3: choose (3,6) → 3×gcd(3,6) = 3×3 = 9. Total score = 1 + 4 + 9 = 14.

Example 2 — Same Elements

$ Input: nums = [3,4,6,8]

› Output: 11

💡 Note: Optimal sequence: Operation 1: choose (3,6) → 1×gcd(3,6) = 1×3 = 3. Operation 2: choose (4,8) → 2×gcd(4,8) = 2×4 = 8. Total score = 3 + 8 = 11.

Example 3 — Minimum Case

$ Input: nums = [1,2]

› Output: 1

💡 Note: Only one operation possible: choose (1,2) → 1×gcd(1,2) = 1×1 = 1.

Constraints

1 ≤ n ≤ 7
1 ≤ nums[i] ≤ 10⁶
nums.length == 2 * n

Visualization

Tap to expand

Understanding the Visualization

Input

Array of 2n positive integers

Process

Choose pairs strategically - save high GCD pairs for later operations

Output

Maximum possible score from n operations

Key Takeaway

🎯 Key Insight: Save pairs with highest GCD for later operations since they get multiplied by larger operation numbers

Asked in

G Google 15 M Microsoft 12 A Amazon 8

The key insight is to use dynamic programming with bitmask to track which elements have been used, avoiding redundant calculations. The optimal approach uses memoization to store results for each state. Time: O(2^(2n) × n²), Space: O(2^(2n))

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Backtracking	O((2n)!)	O(n)	Try all possible ways to pair elements recursively
Dynamic Programming with Bitmask	O(2^(2n) × n²)	O(2^(2n))	Use memoization with bitmask to avoid recalculating same states

Brute Force Backtracking — Algorithm Steps

For operation i, try all pairs of remaining elements
Calculate score i * gcd(pair) for each pair
Recursively solve for remaining elements
Return maximum score across all possibilities

Visualization

Tap to expand

Step-by-Step Walkthrough

Operation 1

Try all pairs, pick one with highest score

Operation 2

From remaining elements, try all pairs again

Continue

Repeat until all elements are used

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int backtrack(int* remaining, int size, int operation, int n) {
    if (operation > n) {
        return 0;
    }
    
    int maxScore = 0;
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            int x = remaining[i];
            int y = remaining[j];
            int score = operation * gcd(x, y);
            
            int* newRemaining = (int*)malloc((size - 2) * sizeof(int));
            int idx = 0;
            for (int k = 0; k < size; k++) {
                if (k != i && k != j) {
                    newRemaining[idx++] = remaining[k];
                }
            }
            
            int totalScore = score + backtrack(newRemaining, size - 2, operation + 1, n);
            if (totalScore > maxScore) {
                maxScore = totalScore;
            }
            
            free(newRemaining);
        }
    }
    
    return maxScore;
}

int solution(int* nums, int size) {
    int n = size / 2;
    return backtrack(nums, size, 1, n);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[20];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((2n)!)

For each operation, we try all remaining pairs, leading to factorial time complexity

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth is n operations

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler