×

CAKEWALK

# PREREQUISITES:

Greatest Common Divisor

# 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

1951916
accept rate: 0%

19.1k348495534

 0 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 1●1 accept rate: 0%
 0 The GCD should be divisible by k Hence, since $2$ is divisible by $1$ , the answer is zero answered 31 May '15, 16:53 3★vozille 1●1 accept rate: 0%

Got it. i did mistake in reading the question. sorry for silly question.

11
accept rate: 0%

# define min(a,b) a<b?a:b;

int main() { long long int a,b,n,k,i,c[100000]; int t; scanf("%d",&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,k-a); count+=b; } printf("%lld\n",count); } return 0; } why my answer gives wrong answer

(26 Jan, 22:45)
 0 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 41●1●4 accept rate: 50% 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)
 0 INT_MAX = Maximum value for an object of type int in c = 32767 (2^15-1) 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 26●1 accept rate: 16%

# 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,k-a); count+=b; } printf("%lld\n",count); } return 0; } why my answer gives wrong answer

This answer is marked "community wiki".

594
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×14,828
×1,481
×282
×128

question asked: 27 May '15, 15:54

question was seen: 6,167 times

last updated: 26 Jan, 22:47