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 2m states, that is, the range of k is [0, 2m - 1].
Enumerate all states from small to large, for each state k, first determine whether the number of 1s 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 cnt⁄2 × g[i][j], update the maximum value of f[k].
The final answer is f[2m - 1].
The time complexity is O(2m × m2), and the space complexity is O(2m). Here, m is the number of elements in the array nums.
PythonJavaC++GoTypeScript
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](code-box)
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);
}
}(code-box)
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];
}
};(code-box)
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)
}(code-box)
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;
}(code-box)
