Ctrl K

GCD Times Sum

Hard
You are given an array of positive integers values and an integer min_len. The weight of a contiguous stretch of the array is the sum of its elements multiplied by their greatest common divisor. Return the largest weight over all contiguous stretches with at least min_len elements.
Example 1
values=[3, 6, 6, 2, 9], min_len=2 → 72

The stretch [6, 6] has gcd 6 and sum 12, giving 72. The stretch [3, 6, 6] gives only 3 · 15 = 45.

Example 2
values=[5, 1, 8], min_len=1 → 64

The single element 8: gcd 8, sum 8, result 64.

Example 3
values=[4, 8, 12, 7], min_len=3 → 96
Constraints
  • 1 ≤ len(values) ≤ 10⁵
  • 1 ≤ values[i] ≤ 10⁶
  • 1 ≤ min_len ≤ len(values)
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsK-th Postage With One Stamp Type HardPair GCDs by Sorted Position HardShave Primes Into Order MediumNumbers From Working Keys HardBiggest Shared-Factor Group Hard
loading Python…
Input
values=[3, 6, 6, 2, 9], min_len=2
Expected
72

Run checks the first 3 tests in your browser. Submit checks all 99 tests on the server, hidden ones included.