I am solving this problem but could not understand how to solve it efficiently.
Problem : you are given N numbers (a_i can be up to 10^6 and n can be up to 3*10^5). in one operation you can change a_i to a_i — 1 or a_i + 1 , find minimum operations to make gcd(a_1 , a_2 , . . . , a_n) > 1.
What I am thinking is , from i = 2 to max(a_i) for each number check how many operations are required to make gcd = i and print the minimum cost.
but the complexity of this approach is O(N*max(a_i)) which is resulting in TLE.
if you can only give hint I will try to learn and solve this problem.
thank you for your time.