values of length n. A cut after index i (with 0 ≤ i ≤ n - 2) splits the array into two non-empty parts: the elements at indices 0..i and all the rest.
A cut is clean when the product of the left part and the product of the right part are coprime, meaning their greatest common divisor is 1.
Return the smallest index i after which the cut is clean, or -1 if there is no clean cut.
The products can get enormous, so multiplying the numbers out directly is not the way to go.values=[6, 10, 7, 21, 11] → 3
After index 0 the factor 2 is shared (6 and 10), after index 1 the factor 3 (60 and 21), after index 2 the factors 3 and 7. After index 3 the left product is 6·10·7·21 = 8820 and the right one is 11, which share nothing, so the answer is 3.
values=[4, 9, 2, 3] → -1
The left side always contains 4 (factor 2), so any cut with 2 still on the right fails; after index 2 the right side is 3 while the left has 9, again sharing 3. No clean cut exists.
values=[1, 1] → 0
1 and 1 are coprime, so the very first cut, after index 0, already works.
values=[6, 10, 7, 21, 11]
3
Run checks the first 3 tests in your browser. Submit checks all 106 tests on the server, hidden ones included.