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, kr) else ans += kr AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here Tester's solution can be found here asked 27 May '15, 15:54

I think test cases are weak as if consider the test case where t=1 n=2 k=1 and numbers are 4,10. GCD of 4 & 10 is 2 which is not equal to 1 but the solution gets accepted showing answer equals to 0. answered 31 May '15, 16:45

Hence, since $ 2 $ is divisible by $ 1 $ , the answer is zero answered 31 May '15, 16:53

I submitted the code using the above pseudo code but got only 20 points. It failed for Task 3. Please help. My code: http://www.codechef.com/viewsolution/7056995 answered 01 Jun '15, 13:25
I got it mohitbura. long long should be used only for the answer while int would work for n and k also.
(01 Jun '15, 16:56)
Did the same mistake :P superfluously 10^9 can be added 10^5 times .
(01 Jun '15, 20:01)

INT_MAX = Maximum value for an object of type int in c = 32767 (2^151) your values of n and k are 10^5 and 10^9 respectively. taking input as int leads to a overflow and a change of values of these numbers. use long and long long for n and k. answered 01 Jun '15, 15:09

include<stdio.h>define min(a,b) a<b?a:b;int main() { long long int a,b,n,k,i,c[100000]; int t; scanf("%lld",&t); while(t) { long long int count=0; scanf("%lld %lld",&n,&k); for(i=0;i<n;i++) { scanf("%lld",&c[i]); a=c[i]%k; b=min(a,ka); count+=b; } printf("%lld\n",count); } return 0; } why my answer gives wrong answer
link
This answer is marked "community wiki".
answered 26 Jan, 22:38
