Bit Manipulation
Array
Math
Dynamic Programming
Backtracking
Bitmask
Number Theory
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
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
.
Python3 Java C++ Go TypeScript
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 ;
}
GitHub