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 <= 7nums.length == 2 * n1 <= nums[i] <= 106
Solutions#
Solution 1: State Compression + Dynamic Programming#
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;
}
|
