Intel Interview Question
Software Engineer / Developerseuclid s algorithm
int gcd ( int a, int b ) {
if ( b == 0 )
return a;
else return gcd ( b , a - b * ( a / b ) );
}
we should find all the factors of the two numbers,
for (i=0;i<n;i++)
{
if(n%i ==0)
factor[j] = n;
j++;
}
factor would be array that is storing all factors of the number. similarly we can get for second number. one thing we can check is whether the number is even or odd, if its odd, then 2,4,6,8,0 or any even number cannnot be a factor of that and will save half of the computation.
then we can check the length of factor array and start with the one that has less elements, because of our loop, the factor array will contain elements in sorted manner. we can then check from the smaller array and then return the answer.
please give comments if this sounds ok or not
public class Numbers {
public static int gcdTC(int a,int b){
int result;
try{
result = (a > b) ? gcd(b, (a%b) ) : gcd(a, (b%a) );
}catch(ArithmeticException ex){
result = (a == 0) ? a : b;
}
return result;
}
public static void main(String[] args){
int x = gcd(12,12);
System.out.println("GCD is == " + x);
}
}
hm... i'm not sure :(
- Zaphod April 02, 2010