LEDIV - Editorial

PROBLEM LINK

Practice
Contest

DIFFICULTY

SIMPLE

PREREQUISITES

Simple Math

PROBLEM

You are given a list of numbers. You have to find the smalelst number which divides all these numbers.

QUICK EXPLANATION

To the initiated, this question should be a breeze.

  • Find the GCD of the list of numbers.
  • Find the smallest prime factor of the GCD.

EXPLANATION

The GCD of two numbers can be found using the Euclid’s Algorithm.

gcd(a,b)
    return (b == 0) ?
        a : gcd(b, (a mod b))

The GCD of a list of numbers A[1 … N] can be found as

let G = 0

for i = 1 to N
    G = gcd( A[i], G )

The above is intuitive and easy to prove by induction.

Now, the next step is to find the smallest prime factor of the GCD. Calculating this can be done in O(sqrt(N)) time easily.

for i = 2 to floor(sqrt(G))
    if G is divisible by i
        return i
return G  // Since G is prime!

This calculation is probably the most time consuming step in the solution. Although, iterating till sqrt(G) will fit within the time limit, you can make one optimization to make it faster. That optimization is pre-calculation! You can pre-calculate the smallest primes in the factorization of any number by sieving.

Consider the snippet below

smallestPrime[ 2 ... N ] // We will store our answers here
for i = 2 to N
    smallestPrime[i] = i
for i = 2 to N
    if smallestPrime[i] = i
        for j = 2*i to N, step-size i
            smallestPrime[j] = min( smallestPrime[j], i )

Notice how we modify the step in which in the usual Sieve of Eratosthenes, we set the multiples of i as non-prime. In this step now, we are simply updating the smallestPrime array at index j. This is a very clever trick to master while solving problems. When you deal with a problem where you need to perform an operation based on all prime factors of a number (like in this case, we wanted to find the smallest of them), a small code snippet like above is usually needed.

SETTERS SOLUTION

Can be found here.

TESTERS SOLUTION

Can be found here.

9 Likes

@admin will you please forward a case where submission 1563837 fails . ?

if we check the array elements by dividing with the prime numbers upto the square root of maximum element of the array.

following this i got WA, can you please give flaw in this approach.

my submission id 1565051

1 Like

http://www.codechef.com/viewsolution/1565258

@admin where is my code failing?

An alternative solution, maybe one that is slightly easier to understand, would be to find all the divisors of the first number, then try each of these divisors on all others numbers and check if they are divisible by it also.

1 Like

http://www.codechef.com/viewsolution/1565594

@admin : Can u tell for which cases it is generating wrong anwers ?

#include<stdio.h>
#include<math.h>
long p[1000],y[100005]={0},x[100005];
void sieve()
{
long i,j;
for(i=3;i<=316;i+=2)
if(y[i]==0)
for(j=i*i;j<=100000;j+=i+i)
y[j]=1;
p[0]=2;
j=0;
for(i=3;i<=100000;i+=2)
if(y[i]==0)
p[++j]=i;
}
int main()
{
long t,n,i,j;
sieve();
scanf("%ld",&t);
while(t–)
{
scanf("%ld",&n);
long min=10000000,f=1;
for(i=0;i<n;++i)
{
scanf("%ld",&x[i]);
if(min>x[i])
min=x[i];
}
for(i=0;p[i]<=min;++i)
{
for(j=0;j<n;++j)
if(x[j]%p[i])
break;
if(j==n)
{
printf("%ld\n",p[i]);
f=0;
break;
}
}
if(f)
printf("-1\n");
}
return 0;

}

i know this approach is not good but i want to know the mistake i made.please reply.thanks in advance.

http://www.codechef.com/viewsolution/1565687
i should get TLE…but getting WA .just want to know which test case solution fails…

i used the same method as given in this editorial but still getting TLE plzz can anyone tell me why i m getting TLE
http://www.codechef.com/viewsolution/1641999

When T and N are constrained to 100000, how come the tester’s solution pass with data type “int” used?

CodeChef: Practical coding for everyone What’s wrong in my code? It shows WA. I’ve implemented the method shown in the editorial. Please help.

i am getting a WA…
please help…

#include<stdio.h>
long int a[100000]={0};
int main(void)
{
 long int t,n,i,min,flag,j,res;
 min=100000;
 scanf("%ld",&t);
 while(t--)
 {
  scanf("%ld",&n);
  for(i=0;i<n;i++)
  {
   scanf("%ld",&a[i]);
   if(a[i]<min)
   {
    min=a[i];
   }
  }
  for(i=2;i<=min;i++)
  {
   flag=1;
   for(j=0;j<n;j++)
   {
    if(a[j]%i!=0)
    {
     flag=0;
     break;
    }
   }
   if(flag==1)
   {
    res=i;
    break;
   }
  }
  if(flag==0)
  {
   res=-1;
  }
  printf("%ld\n",res);
 }
 return 0;
}

i am getting a WA… please help…

#include<stdio.h>
int main(void)
{
 int t,ds,dt,d,x;
 x=0;
 scanf("%d",&t);
 while(t--)
 {
  scanf("%d%d%d",&ds,&dt,&d);
  if(ds+dt<d)
  {
   printf("%.6f\n",(float)(d-dt-ds));
  }
  else
  {
   printf("%.6f\n",(float)(x));
  }
 }
 return 0;
}

https://www.codechef.com/viewsolution/13098242
can somebody tell me, for which case it is not working???

I am getting WA.Please tell me the case where my code fails.
https://www.codechef.com/viewsolution/14322036

I am getting wrong answer although in the dry run everything seems to be working fine. Also, the sample test cases from editorial are working.

Can anyone suggest the test case which could fail my solution/ review my solution?

https://www.codechef.com/viewsolution/14364283

TestCases:

1 1 1 => -1 (since x>1)

1 2 20122 30183 => 10061

1 1 24371 => 24371

1 2 123 456 => 3

Many Thanks!

When your ‘r’ is divisible by 3 you did not find this. Say r=63.

1 Like

That was a huge miss … sorry . .
but sadly that does not fix the error
submission 1565280

Consider T=1 N=1 A[1]=24371

2 Likes

You logic is completely incorrect. Try this test T=1 N=2 A[1] = 2 * P A[2] = 3 * P where P is large prime say A[1] = 20122, A[2] = 30183.

1 Like