values of n positive integers. In one operation you pick two neighbouring elements and replace one of them (your choice) with their greatest common divisor (gcd).
Return the smallest number of operations after which every element equals 1, or -1 if that cannot be achieved.values=[6, 10, 15] → 4
No pair of neighbours has a gcd of 1, but the whole triple does. The first 1 takes 2 operations: [6, 10, 15] → [6, 5, 15] → [1, 5, 15]. Two more spread it to the right: [1, 1, 15] → [1, 1, 1]. Total: 4.
values=[4, 1, 8, 2] → 3
There is already a 1, and each of the other three numbers becomes 1 in one operation with a neighbour that is 1.
values=[6, 9, 12] → -1
Every number is divisible by 3, so every gcd will be too and a 1 can never appear. The answer is -1.
values=[6, 10, 15]
4
Run checks the first 3 tests in your browser. Submit checks all 160 tests on the server, hidden ones included.