Segments With a Given GCD

Medium

You are given an array of positive integers values and a number divisor. Count the non-empty segments (contiguous pieces of the array) whose elements have a greatest common divisor of exactly divisor. The GCD of a set of numbers is the largest positive integer that divides each of them. Segments with different bounds count separately.

Example 1

values=[12, 8, 6, 5, 4], divisor=4 → 2

Exactly 4 is the GCD of [12, 8] and [4]. The GCD of [8] alone is 8, and once 6 joins a segment, the GCD drops to 2.

Example 2

values=[7, 7], divisor=7 → 3

All three segments, [7], [7] and [7, 7], have GCD 7.

Example 3

values=[3, 5, 9], divisor=2 → 0

Constraints

1 ≤ len(values) ≤ 1000
1 ≤ values[i] ≤ 10⁹
1 ≤ divisor ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math Number Theory

Similar problems

Primes Below a Bound Medium Photo Frames of the Same Shape Medium Segments on a Chart Medium Chunks With a Common Divisor Medium Split by Shared Ends Medium

Input

values=[12, 8, 6, 5, 4], divisor=4

Expected

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