Little Elephant and Divisors-Help for Saving TLE.

help
, , ,
1

Problem Link->https://www.codechef.com/problems/LEDIV/
My Solution–>

#include<iostream.h>
#include<stdio.h>
int main()
{

    int t=0;

   cin>>t;

     while(t!=0)
    {
        int n=0;

      scanf("%d",&n);

        int min=100001;
      
        long *arr=new long[n];

        for(int i=0;i<n;i++)
       {
          scanf("%ld",&arr[i]);       

        if(arr[i]<min)  
            min=arr[i];
       }
    
    
  
 int i=2; 

 int count=0;

 int ans=0;

bool flag=false;

 while(i<=min && flag==false)
 {

              count=0;

        for(int k=0;k<n;k++)
       {        

            if(arr[k]%i==0)
                   count++;              
        }
        if(count==n)
       {  
              ans=i;  

              flag=true;

              break;
       }
   
          i++;
          

 }

 if(flag==true)
            printf("%d",ans);

 else
            printf("-1");
       
    t--;
printf("\n");


}
 return 0;
}
2

Answer is always prime or -1.
One way to do it, first find all prime numbers less than 100000, store it somewhere(preprocessing).
So in solution instead of looping through all i(2 to min(ar)) loop through prime factor that you need(i.e largest prime number for your min element(2 to largest prime factor for min element) ).

1 Like
3

What can i change in this code?

4

Dude i just cant tell in one comment what to change. Figure it out yourself. You need to change all of it(|| most of it).

5

Okay i accepted your answer,And respect for your effort(comment)

6

I think for each case, we have to find the lease divisor of all the numbers which is >1. So, basically answer has to be one of the divisor of GCD of all the numbers.

Algo:

  1. Calculate GCD of all numbers in the given array.

  2. If gcd = 1, then answer is -1, and return.

  3. Find minimum divisor of gcd other than 1. (If gcd is prime, then gcd itself is the answer)

Here’s my solution:

https://code.hackerearth.com/676ee8a

1 Like