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

8 Likes

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

``````#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.

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)
``````

1 Like

why does my code shows time limit exeeded
http://www.codechef.com/viewsolution/5667075

Will this code not run in O(n) time ?.
Can the improvement of O(n) to O(nlogn) be done by recursion by dividing the array into halves at each step and reaching the base case of two elements whose gcd can be found by actual definition (by running a for loop for the two elements).

i have used some other logic. can someone please give me some specific test cases to check?

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

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