Array
Math
Binary Search
Number Theory
Description
You are given an array of integers nums
and an integer k
.
The gcd-sum of an array a
is calculated as follows:
Let s
be the sum of all the elements of a
.
Let g
be the greatest common divisor of all the elements of a
.
The gcd-sum of a
is equal to s * g
.
Return the maximum gcd-sum of a subarray of nums
with at least k
elements.
Example 1:
Input: nums = [2,1,4,4,4,2], k = 2
Output: 48
Explanation: We take the subarray [4,4,4], the gcd-sum of this array is 4 * (4 + 4 + 4) = 48.
It can be shown that we can not select any other subarray with a gcd-sum greater than 48.
Example 2:
Input: nums = [7,3,9,4], k = 1
Output: 81
Explanation: We take the subarray [9], the gcd-sum of this array is 9 * 9 = 81.
It can be shown that we can not select any other subarray with a gcd-sum greater than 81.
Constraints:
n == nums.length
1 <= n <= 105
1 <= nums[i] <= 106
1 <= k <= n
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def maxGcdSum ( self , nums : List [ int ], k : int ) -> int :
s = list ( accumulate ( nums , initial = 0 ))
f = []
ans = 0
for i , v in enumerate ( nums ):
g = []
for j , x in f :
y = gcd ( x , v )
if not g or g [ - 1 ][ 1 ] != y :
g . append (( j , y ))
f = g
f . append (( i , v ))
for j , x in f :
if i - j + 1 >= k :
ans = max ( ans , ( s [ i + 1 ] - s [ j ]) * x )
return ans
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 class Solution {
public long maxGcdSum ( int [] nums , int k ) {
int n = nums . length ;
long [] s = new long [ n + 1 ] ;
for ( int i = 1 ; i <= n ; ++ i ) {
s [ i ] = s [ i - 1 ] + nums [ i - 1 ] ;
}
List < int []> f = new ArrayList <> ();
long ans = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
List < int []> g = new ArrayList <> ();
for ( var e : f ) {
int j = e [ 0 ] , x = e [ 1 ] ;
int y = gcd ( x , nums [ i ] );
if ( g . isEmpty () || g . get ( g . size () - 1 ) [ 1 ] != y ) {
g . add ( new int [] { j , y });
}
}
f = g ;
f . add ( new int [] { i , nums [ i ] });
for ( var e : f ) {
int j = e [ 0 ] , x = e [ 1 ] ;
if ( i - j + 1 >= k ) {
ans = Math . max ( ans , ( s [ i + 1 ] - s [ j ] ) * x );
}
}
}
return ans ;
}
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
30 class Solution {
public :
long long maxGcdSum ( vector < int >& nums , int k ) {
int n = nums . size ();
long long s [ n + 1 ];
s [ 0 ] = 0 ;
for ( int i = 1 ; i <= n ; ++ i ) {
s [ i ] = s [ i - 1 ] + nums [ i - 1 ];
}
vector < pair < int , int >> f ;
long long ans = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
vector < pair < int , int >> g ;
for ( auto [ j , x ] : f ) {
int y = gcd ( x , nums [ i ]);
if ( g . empt () || g . back (). second != y ) {
g . emplace_back ( j , y );
}
}
f = move ( g );
f . emplace_back ( i , nums [ i ]);
for ( auto [ j , x ] : f ) {
if ( i - j + 1 >= k ) {
ans = max ( ans , ( s [ i + 1 ] - s [ j ]) * x );
}
}
}
return ans ;
}
};
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 func maxGcdSum ( nums [] int , k int ) int64 {
n := len ( nums )
s := make ([] int64 , n + 1 )
s [ 0 ] = 0
for i , x := range nums {
s [ i + 1 ] = s [ i ] + int64 ( x )
}
type pair [ 2 ] int
var f [] pair
var ans int64
for i := 0 ; i < n ; i ++ {
var g [] pair
for _ , p := range f {
j , x := p [ 0 ], p [ 1 ]
y := int ( gcd ( int ( x ), nums [ i ]))
if len ( g ) == 0 || g [ len ( g ) - 1 ][ 1 ] != y {
g = append ( g , pair { j , y })
}
}
f = g
f = append ( f , pair { i , nums [ i ]})
for _ , p := range f {
j , x := p [ 0 ], p [ 1 ]
if i - j + 1 >= k {
ans = max ( ans , ( s [ i + 1 ] - s [ j ]) * int64 ( x ))
}
}
}
return ans
}
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 function maxGcdSum ( nums : number [], k : number ) : number {
const n : number = nums . length ;
const s : number [] = Array ( n + 1 ). fill ( 0 );
for ( let i = 1 ; i <= n ; i ++ ) {
s [ i ] = s [ i - 1 ] + nums [ i - 1 ];
}
let f : [ number , number ][] = [];
let ans : number = 0 ;
for ( let i = 0 ; i < n ; ++ i ) {
const g : [ number , number ][] = [];
for ( const [ j , x ] of f ) {
const y : number = gcd ( x , nums [ i ]);
if ( g . length === 0 || g . at ( - 1 )[ 1 ] !== y ) {
g . push ([ j , y ]);
}
}
f = g ;
f . push ([ i , nums [ i ]]);
for ( const [ j , x ] of f ) {
if ( i - j + 1 >= k ) {
ans = Math . max ( ans , ( s [ i + 1 ] - s [ j ]) * x );
}
}
}
return ans ;
}
function gcd ( a : number , b : number ) : number {
return b === 0 ? a : gcd ( b , a % b );
}
Solution 2
TypeScript
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 function maxGcdSum ( nums : number [], k : number ) : number {
const n : number = nums . length ;
const s : number [] = Array ( n + 1 ). fill ( 0 );
for ( let i = 1 ; i <= n ; i ++ ) {
s [ i ] = s [ i - 1 ] + nums [ i - 1 ];
}
let f : [ number , number ][] = [];
let ans : number = 0 ;
for ( let i = 0 ; i < n ; ++ i ) {
const g : [ number , number ][] = [];
for ( const [ j , x ] of f ) {
const y : number = gcd ( x , nums [ i ]);
if ( g . length === 0 || g . at ( - 1 )[ 1 ] !== y ) {
g . push ([ j , y ]);
}
}
f = g ;
f . push ([ i , nums [ i ]]);
for ( const [ j , x ] of f ) {
if ( i - j + 1 >= k ) {
ans = Math . max ( ans , ( s [ i + 1 ] - s [ j ]) * x );
}
}
}
return ans ;
}
function gcd ( a : number , b : number ) : number {
return b === 0 ? a : gcd ( b , a % b );
}
GitHub