AMSGAME1 - Editorial

editorial
, , , ,
1

Problem Link:

Practice

Contest

Difficulty:

CAKEWALK

Pre-requisites:

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
2

wat is my mistake in the code? CodeChef: Practical coding for everyone
the response is wrong answer

3

I Have no Idea About this Method I used some Other method

#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
    be the answer

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
hence answer will be 1 :slight_smile:

5 Likes
4

someone please tell why i am getting wrong answer in following code : CodeChef: Practical coding for everyone OR please provide me with some test cases with which i could figure out my mistake.

5

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)

For help regarding the reduce function, see this page.

Source: An answer on StackOverflow

1 Like
6

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

7

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

8

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

9

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. :slight_smile: The fast way to compute GCD is called the Euclidean algorithm, read about it.

2 Likes
10

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