Where the Product Adds Up

Easy

You are given an array of positive integers values. Call a contiguous segment of the array **fair** if the product of its elements equals the product of their LCM and GCD: prod(segment) == lcm(segment) * gcd(segment) Here prod is the product of all numbers in the segment, lcm is their least common multiple and gcd is their greatest common divisor. Return the length of the longest fair segment.

Example 1

values=[2, 1, 3, 1, 4, 4, 1] → 4

Take [2, 1, 3, 1, 4]: the product is 24, the GCD is 1, the LCM is 12, and 12 · 1 = 24. Adding the second 4 breaks it: the product becomes 96 while the LCM and GCD stay the same.

Example 2

values=[6, 6, 6, 6] → 2

Any two neighbours work: 6 · 6 = 36 = 6 · 6. Three 6s do not: 216 ≠ 36.

Example 3

values=[1, 1, 5, 7, 1] → 5

Constraints

2 ≤ len(values) ≤ 2000
1 ≤ values[i] ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math Enumeration Number Theory Sliding Window

Similar problems

Primes Below a Bound Medium A Number as Two Primes Medium Primes Along Grid Rays Medium Even Piles of Cards Easy XOR of Every Subset Easy

Input

values=[2, 1, 3, 1, 4, 4, 1]

Expected

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