Maximize Score After N Operations Problem

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, 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.

Examples

Example 1:

1
2
3
4
5
6

Input:
nums = [1,2]
Output:
 1
Explanation: The optimal choice of operations is:
(1 * gcd(1, 2)) = 1

Example 2:

1
2
3
4
5
6

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:

1
2
3
4
5
6

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

Solution

Method 1 – Bitmask Dynamic Programming

Intuition

We use bitmask DP to represent which numbers have been used. For each operation, we try all pairs of unused numbers, calculate the score, and recursively solve for the remaining numbers. Memoization helps avoid recomputation.

Approach

  1. Precompute gcd for all pairs in nums.
  2. Use a DP array where dp[mask] is the max score for the current set of unused numbers (mask).
  3. For each mask, try all pairs of unused numbers:
    • Mark them as used, calculate score for this operation, and recurse.
    • Track the maximum score.
  4. The answer is dp[full_mask] (all numbers unused).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int maxScore(vector<int>& nums) {
        int n = nums.size(), m = n/2;
        vector<vector<int>> g(n, vector<int>(n));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                g[i][j] = gcd(nums[i], nums[j]);
        vector<int> dp(1<<n);
        for (int mask = 0; mask < (1<<n); ++mask) {
            int cnt = __builtin_popcount(mask);
            if (cnt % 2) continue;
            for (int i = 0; i < n; ++i) {
                if (!(mask & (1<<i))) continue;
                for (int j = i+1; j < n; ++j) {
                    if (!(mask & (1<<j))) continue;
                    int new_mask = mask ^ (1<<i) ^ (1<<j);
                    int op = m - cnt/2 + 1;
                    dp[mask] = max(dp[mask], dp[new_mask] + op * g[i][j]);
                }
            }
        }
        return dp[(1<<n)-1];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

func maxScore(nums []int) int {
    n, m := len(nums), len(nums)/2
    g := make([][]int, n)
    for i := range g {
        g[i] = make([]int, n)
        for j := range g[i] {
            g[i][j] = gcd(nums[i], nums[j])
        }
    }
    dp := make([]int, 1<<n)
    for mask := 0; mask < 1<<n; mask++ {
        cnt := bits.OnesCount(uint(mask))
        if cnt%2 != 0 {
            continue
        }
        for i := 0; i < n; i++ {
            if mask&(1<<i) == 0 {
                continue
            }
            for j := i+1; j < n; j++ {
                if mask&(1<<j) == 0 {
                    continue
                }
                newMask := mask ^ (1<<i) ^ (1<<j)
                op := m - cnt/2 + 1
                dp[mask] = max(dp[mask], dp[newMask]+op*g[i][j])
            }
        }
    }
    return dp[(1<<n)-1]
}
func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    public int maxScore(int[] nums) {
        int n = nums.length, m = n/2;
        int[][] g = new int[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                g[i][j] = gcd(nums[i], nums[j]);
        int[] dp = new int[1<<n];
        for (int mask = 0; mask < (1<<n); ++mask) {
            int cnt = Integer.bitCount(mask);
            if (cnt % 2 != 0) continue;
            for (int i = 0; i < n; ++i) {
                if ((mask & (1<<i)) == 0) continue;
                for (int j = i+1; j < n; ++j) {
                    if ((mask & (1<<j)) == 0) continue;
                    int newMask = mask ^ (1<<i) ^ (1<<j);
                    int op = m - cnt/2 + 1;
                    dp[mask] = Math.max(dp[mask], dp[newMask] + op * g[i][j]);
                }
            }
        }
        return dp[(1<<n)-1];
    }
    private int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    fun maxScore(nums: IntArray): Int {
        val n = nums.size
        val m = n/2
        val g = Array(n) { IntArray(n) }
        for (i in 0 until n)
            for (j in 0 until n)
                g[i][j] = gcd(nums[i], nums[j])
        val dp = IntArray(1 shl n)
        for (mask in 0 until (1 shl n)) {
            val cnt = mask.countOneBits()
            if (cnt % 2 != 0) continue
            for (i in 0 until n) {
                if (mask and (1 shl i) == 0) continue
                for (j in i+1 until n) {
                    if (mask and (1 shl j) == 0) continue
                    val newMask = mask xor (1 shl i) xor (1 shl j)
                    val op = m - cnt/2 + 1
                    dp[mask] = maxOf(dp[mask], dp[newMask] + op * g[i][j])
                }
            }
        }
        return dp[(1 shl n)-1]
    }
    private fun gcd(a: Int, b: Int): Int {
        var x = a; var y = b
        while (y != 0) {
            val t = y; y = x % y; x = t
        }
        return x
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def maxScore(self, nums: list[int]) -> int:
        from math import gcd
        n, m = len(nums), len(nums)//2
        g = [[gcd(nums[i], nums[j]) for j in range(n)] for i in range(n)]
        dp = [0] * (1<<n)
        for mask in range(1<<n):
            cnt = bin(mask).count('1')
            if cnt % 2 != 0:
                continue
            for i in range(n):
                if not (mask & (1<<i)):
                    continue
                for j in range(i+1, n):
                    if not (mask & (1<<j)):
                        continue
                    new_mask = mask ^ (1<<i) ^ (1<<j)
                    op = m - cnt//2 + 1
                    dp[mask] = max(dp[mask], dp[new_mask] + op * g[i][j])
        return dp[(1<<n)-1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

impl Solution {
    pub fn max_score(nums: Vec<i32>) -> i32 {
        fn gcd(mut a: i32, mut b: i32) -> i32 {
            while b != 0 {
                let t = b; b = a % b; a = t;
            }
            a
        }
        let n = nums.len();
        let m = n/2;
        let mut g = vec![vec![0; n]; n];
        for i in 0..n {
            for j in 0..n {
                g[i][j] = gcd(nums[i], nums[j]);
            }
        }
        let mut dp = vec![0; 1<<n];
        for mask in 0..(1<<n) {
            let cnt = mask.count_ones();
            if cnt % 2 != 0 { continue; }
            for i in 0..n {
                if mask & (1<<i) == 0 { continue; }
                for j in i+1..n {
                    if mask & (1<<j) == 0 { continue; }
                    let new_mask = mask ^ (1<<i) ^ (1<<j);
                    let op = m - cnt/2 + 1;
                    dp[mask as usize] = dp[mask as usize].max(dp[new_mask as usize] + op as i32 * g[i][j]);
                }
            }
        }
        dp[(1<<n)-1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    maxScore(nums: number[]): number {
        const n = nums.length, m = n/2
        const g = Array.from({length: n}, () => Array(n).fill(0))
        for (let i = 0; i < n; ++i)
            for (let j = 0; j < n; ++j)
                g[i][j] = gcd(nums[i], nums[j])
        const dp = Array(1<<n).fill(0)
        for (let mask = 0; mask < (1<<n); ++mask) {
            const cnt = countBits(mask)
            if (cnt % 2 !== 0) continue
            for (let i = 0; i < n; ++i) {
                if (!(mask & (1<<i))) continue
                for (let j = i+1; j < n; ++j) {
                    if (!(mask & (1<<j))) continue
                    const newMask = mask ^ (1<<i) ^ (1<<j)
                    const op = m - Math.floor(cnt/2) + 1
                    dp[mask] = Math.max(dp[mask], dp[newMask] + op * g[i][j])
                }
            }
        }
        return dp[(1<<n)-1]
    }
}
function gcd(a: number, b: number): number {
    while (b !== 0) {
        [a, b] = [b, a % b]
    }
    return a
}
function countBits(x: number): number {
    let cnt = 0
    while (x) {
        cnt += x & 1
        x >>= 1
    }
    return cnt
}

Complexity

  • ⏰ Time complexity: O(n^2 * 2^n) — For each mask, we try all pairs.
  • 🧺 Space complexity: O(2^n) — For the DP array.

Method 2 – Backtracking with Pruning

Intuition

Try all possible pairings using backtracking, but prune branches that cannot beat the current best score. This is slower but can be useful for small n.

Approach

  1. Precompute gcd for all pairs.
  2. Use backtracking to try all pairings:
    • For each unused pair, mark as used, calculate score, and recurse.
    • Track the maximum score.
    • Prune branches if the remaining possible score cannot beat the current best.
  3. Return the best score found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def maxScore(nums: list[int]) -> int:
    from math import gcd
    n, m = len(nums), len(nums)//2
    g = [[gcd(nums[i], nums[j]) for j in range(n)] for i in range(n)]
    best = 0
    def dfs(op: int, used: int, score: int):
        nonlocal best
        if op > m:
            best = max(best, score)
            return
        for i in range(n):
            if used & (1<<i): continue
            for j in range(i+1, n):
                if used & (1<<j): continue
                dfs(op+1, used | (1<<i) | (1<<j), score + op * g[i][j])
    dfs(1, 0, 0)
    return best

Complexity

  • ⏰ Time complexity: O((2n)!/(n!2^n)) — All pairings, exponential.
  • 🧺 Space complexity: O(n) — For recursion stack.