We are given an array "A" of size "N"
Constraints :
1) 1<=N<=100
2) 1<=A[i]<=30
We have to generate an array "b" of size "N" such that for all pairs (i,j) , gcd(b[i],b[j]) = 1, holds true for array "b" .
The value to be calculated is : abs(A[1]-b[1]) + abs(A[2]-b[2]) + ...... + .... + ..... abs(A[n] — b[n]) = x
We have to minimize the value of 'x'.
How to generate an array "b" which minimizes the value of "x" ?
Example array "A" :- {1,2,4,6,8}
Output array "b" : — {1,2,3,5,7}
and x = 3, which is the minimum possible value.
I got code for this problem in a group : — https://ideone.com/VUyN5p
But still cannot get the idea behind the solution.
First thing to observe is $$$b[i] <= 58$$$. Otherwise we may replace, $$$b[i]$$$ with $$$1$$$ without increasing $$$x$$$. There are only $$$16$$$ primes not larger than $$$58$$$. Each prime may divide at most one of the values in $$$b$$$. We can represent any subset of these primes with a $$$16$$$ bit bitmask. Thus we can do a dp.
$$$dp[i][mask] = $$$ minimum score considering only the first $$$i$$$ indexes using only primes from mask. For transitions, we can simply iterate over all $$$58$$$ possible values of $$$b[i]$$$ and update the mask accordingly.