Practice

Contest

CAKEWALK

gcd

# Problem:

You are given a set of N positive numbers A[0], A[1], …, A[N-1]. At each step you pick two unequal numbers and replace the larger one by the difference. You stop when all numbers are equal. Find at what number will you stop.

# Explanation:

You stop at the GCD of the numbers. To prove this, we just use the fact that gcd(a, b) = gcd(a-b, b), where a > b. Now, let the original GCD be G. After a single step, since gcd(a, b) = gcd(a-b, b), in particular, gcd(A[i], A[j]) = gcd(A[i]-A[j], A[j]), we get that the gcd remains G.

If we finally end at the number K, then gcd(K, K, K, …, K) = K. But since after each step the gcd remains invariant, we get that K = G.

# Setter’s Solution:

Can be found here

# Tester’s Solution:

Can be found here

7 Likes

wat is my mistake in the code? http://www.codechef.com/viewsolution/2172016

Your minimum is 1000, but the numbers can be up to 10^9. A counterexample could be {2000,4000}.
Of course, when you correct this, you will get a TLE. The fast way to compute GCD is called the Euclidean algorithm, read about it.

2 Likes

``````#include<iostream>
using namespace std;

int main(){
int n,t;
cin>>t;
while(t--){
cin>>n;
long long int a[n];
long long int small = 1000000001;
for(int i = 0; i <n;i++){cin>>a[i];
if (small > a[i]) small = a[i];  }

long long int next;
while(1){
if(small == 1){ cout<<1<<endl; break;}
for(int i = 0; i <n;i++){ if(a[i]%small == 0) a[i] = small;
else {a[i] = a[i]%small;
if(a[i]<small) next = a[i];}  }
if(next == small){cout<<small<<endl; break;}
small = next;
}}}
``````

My Approach i will keep track of small and next small (next here)

• if small = 1 then answer must be 1

• if a[i]%small = 0 then a[i] = small
otherwise a[i] = a[i]%small

• in every iteration i will keep track
of smallest number using next
after one iteration if the small and
next small are equal then that will

Example = [6 , 10 , 15]

here small will be 6 so after one iteration the array will be [6 , 10%6 , 15%6] = [6,4,3]
here next small = 3
small(6) != next small(3) so we will iterate it again
small is updated to next small so in next iteration small = 3

now the array will be [3 , 4%3 , 3] = [3,1,3]
here next small = 1
small (3) != next small (1)
so small is updated to 1 and we will iterate again

now small is 1

3 Likes

someone please tell why i am getting wrong answer in following code : http://www.codechef.com/viewsolution/2232651 OR please provide me with some test cases with which i could figure out my mistake.

my min is 1000000001, but still i’m getting WA instead of TLE!
http://www.codechef.com/viewsolution/3974361

If you are using python, you could use the reduce function in python to calculate the GCD of a list of numbers as follows:

``````from fractions import gcd

def get_gcd(list_of_numbers):
return reduce(gcd, list_of_numbers)
``````