PROBLEM LINK:
DIFFICULTY:
CAKEWALK
PREREQUISITES:
PROBLEM:
Given an array A[] of n numbers and k. Find the minimum number of operation (adding or subtracting one from some array position) that should be performed on the array such that the gcd of all the numbers in the modified array is divisible by k.
EXPLANATION:
We are given an array A[], a number k and we can perform only one operation that is adding or subtracting one from some array position, repeatedly modifying the array until the gcd of all the numbers of the array is divisible by k. The problem is to find the minimum number of operation to achieve this. Note that if all the numbers in the array is already divisible by k, then we don’t have to do anything and the answer will be 0.
Now consider the case where some numbers are not divisible by k (hence gcd is not divisible by k). In this case, pick up that number say a[i] = qk + r where r>0 and modify it to either qk or (q+1)k whichever takes minimum number of operations. One final point to note is that all the numbers in the modified array should be positive, so when a[i] < k, we can only increase its value to make it divisible by k. The time complexity of the above algorithm is clearly \mathcal{O}(n). Refer to the following pseudo code for better understanding
for i = 0 to n r = a[i] mod k if(a[i] >= k) ans += min(r, k-r) else ans += k-r
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here
Tester’s solution can be found here