We are provided a set of numbers.
We can increment or decrement any given number by 1. This is denoted as a single operation. The objective is to make the GCD of the entire set of numbers equal to K. We need to find the minimum number of operations required.
In case the GCD was to be some multiple of K, it was easier. Just find the 2 multiples of K nearest to each number, but this doesn't always lead to GCD = K.
What can be the best approach to carry out this task?
I have a solution for smaller constraints based on dynamic programming. Let's say you are given the set $[a_1,a_2,....a_n]$. Now, the intended state for the final sequence will be something like :
$ [x_1*k,x_2*k,....x_3*k] $, where $ gcd(x_1,x_2....x_n) = 1 $ ( $ x_i*k $ is what we replace $ a_i $ with)
Maintain states $ dp[i][j] $ = minimum operations required to get gcd of $ [x_1,x_2...x_i] $ equal to $ j $.
The answer will be $ dp[n][1] $ , where $n$ is the size of the set. The complexity here also depends on the range of values, as you need to try all multiples of $k$ in the range to update the $dp$
