Tester: Suchan Park
Editorialist: Suchan Park
How to compute GCD (Euclidean Algorithm)
You are given a sequence of integers of length N. You are allowed to delete up to N-1 elements in this sequence. Your goal is to make the GCD of the resulting sequence 1. Find whether it is possible, and if it’s possible, find the minimum number of deletions.
It makes no sense to remove any elements, since any such operation doesn’t decrease the GCD and increase the number of deletions. Therefore the answer is 0 if the GCD of the original array is 1, -1 otherwise.
From the definition of GCD, we know that
This means whenever we apply the GCD operation, the value does not increase. Therefore, the longer the sequence is, the smaller the GCD becomes.
Since we want to minimize the GCD and the number of deletions, we can see the best strategy is not deleting any of the elements!
If the GCD of the given sequence is 1, we are done. Otherwise, the GCD will not be 1 even if we delete some elements (since the GCD will not decrease), it is impossible to make the GCD 1.
Therefore the answer is 0 if the GCD of the original array is 1, -1 otherwise.
We can compute the GCD of the whole array by:
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.