Skip to content

1799. Maximize Score After N Operations

Description

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

Solutions

Solution 1: State Compression + Dynamic Programming

Thinking

Each move picks two remaining numbers and scores \(i\cdot\gcd\) on the \(i\)-th move. \(n\le 7\) so \(m=2n\le 14\), and subset DP can try pairings.

Precompute pairwise \(\gcd\). \(f[k]\) is the best score using the elements in mask \(k\). When the popcount is even, try removing a pair \(i,j\) and add \(\textit{cnt}/2\cdot g[i][j]\).

The full mask \(f[2^m-1]\) is the answer.

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 \(1\)s 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxScore(self, nums: List[int]) -> int:
        m = len(nums)
        f = [0] * (1 << m)
        g = [[0] * m for _ in range(m)]
        for i in range(m):
            for j in range(i + 1, m):
                g[i][j] = gcd(nums[i], nums[j])
        for k in range(1 << m):
            if (cnt := k.bit_count()) % 2 == 0:
                for i in range(m):
                    if k >> i & 1:
                        for j in range(i + 1, m):
                            if k >> j & 1:
                                f[k] = max(
                                    f[k],
                                    f[k ^ (1 << i) ^ (1 << j)] + cnt // 2 * g[i][j],
                                )
        return f[-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
class Solution {
    public int maxScore(int[] nums) {
        int m = nums.length;
        int[][] g = new int[m][m];
        for (int i = 0; i < m; ++i) {
            for (int j = i + 1; j < m; ++j) {
                g[i][j] = gcd(nums[i], nums[j]);
            }
        }
        int[] f = new int[1 << m];
        for (int k = 0; k < 1 << m; ++k) {
            int cnt = Integer.bitCount(k);
            if (cnt % 2 == 0) {
                for (int i = 0; i < m; ++i) {
                    if (((k >> i) & 1) == 1) {
                        for (int j = i + 1; j < m; ++j) {
                            if (((k >> j) & 1) == 1) {
                                f[k] = Math.max(
                                    f[k], f[k ^ (1 << i) ^ (1 << j)] + cnt / 2 * g[i][j]);
                            }
                        }
                    }
                }
            }
        }
        return f[(1 << m) - 1];
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % 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
class Solution {
public:
    int maxScore(vector<int>& nums) {
        int m = nums.size();
        int g[m][m];
        for (int i = 0; i < m; ++i) {
            for (int j = i + 1; j < m; ++j) {
                g[i][j] = gcd(nums[i], nums[j]);
            }
        }
        int f[1 << m];
        memset(f, 0, sizeof f);
        for (int k = 0; k < 1 << m; ++k) {
            int cnt = __builtin_popcount(k);
            if (cnt % 2 == 0) {
                for (int i = 0; i < m; ++i) {
                    if (k >> i & 1) {
                        for (int j = i + 1; j < m; ++j) {
                            if (k >> j & 1) {
                                f[k] = max(f[k], f[k ^ (1 << i) ^ (1 << j)] + cnt / 2 * g[i][j]);
                            }
                        }
                    }
                }
            }
        }
        return f[(1 << m) - 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
func maxScore(nums []int) int {
    m := len(nums)
    g := [14][14]int{}
    for i := 0; i < m; i++ {
        for j := i + 1; j < m; j++ {
            g[i][j] = gcd(nums[i], nums[j])
        }
    }
    f := make([]int, 1<<m)
    for k := 0; k < 1<<m; k++ {
        cnt := bits.OnesCount(uint(k))
        if cnt%2 == 0 {
            for i := 0; i < m; i++ {
                if k>>i&1 == 1 {
                    for j := i + 1; j < m; j++ {
                        if k>>j&1 == 1 {
                            f[k] = max(f[k], f[k^(1<<i)^(1<<j)]+cnt/2*g[i][j])
                        }
                    }
                }
            }
        }
    }
    return f[1<<m-1]
}

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%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
33
34
35
36
37
38
39
function maxScore(nums: number[]): number {
    const m = nums.length;
    const f: number[] = new Array(1 << m).fill(0);
    const g: number[][] = new Array(m).fill(0).map(() => new Array(m).fill(0));
    for (let i = 0; i < m; ++i) {
        for (let j = i + 1; j < m; ++j) {
            g[i][j] = gcd(nums[i], nums[j]);
        }
    }
    for (let k = 0; k < 1 << m; ++k) {
        const cnt = bitCount(k);
        if (cnt % 2 === 0) {
            for (let i = 0; i < m; ++i) {
                if ((k >> i) & 1) {
                    for (let j = i + 1; j < m; ++j) {
                        if ((k >> j) & 1) {
                            const t = f[k ^ (1 << i) ^ (1 << j)] + ~~(cnt / 2) * g[i][j];
                            f[k] = Math.max(f[k], t);
                        }
                    }
                }
            }
        }
    }
    return f[(1 << m) - 1];
}

function gcd(a: number, b: number): number {
    return b ? gcd(b, a % b) : a;
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

Comments