Programming Question - Compute GCD - Davide SpataroDavide Spataro

Programming Question: Compute the Greatest Common Divisor of two integers (easy)

This question is divided in two parts: you will first asked to write a function that computes the GCD withouth any space/time constraints. The second part will be more challenching, asking for not using multiplication or division or addition.

Part1: write a function that takes two integers as input and returns their gcd using the famous Euclidean algorithm.

Part 2: compute the Greatest Common Divisor of two integers without using multiplication addition or division operators (easy)

Solutions:

Show Solution

Solution part 1:

It is based on the fact that then

//a > b
int gcdEuler(int a, int b){
	int rem;
	while(b>0){
		rem=a%b;
		a=b;
		b=rem;
	}
	return a;
}

Solution part 2:

Solution is based on the followings:
then both and are even then is clearly .
If is even and is odd then the cannot be even and therefore , respectively . If both numbers are odd and then , respectively

The function is recursive and use bit shift for multiplying and dividing and use bit AND operator to check whether a number is odd or even.

int gcd(int a, int b){
	
	if(a==0)
		return b;
	if(b==0)
		return a;
	
	//both even
	if(!(a & 0x1) & !(b & 0x1))
		return (gcd(a>>1,b>>1) <<1); 
        //both odd 
        if( (a & 0x1) & (b & 0x1)) if(a>b)
		return gcd(a-b,b);
	else
		return gcd(a,b-a);
		
	if(!(a & 0x1))
		return gcd(a>>1,b);

	//if(!(b & 0x1))
		return gcd(a,b>>1);
		
	
	
	
}

Davide Spataro

Non multa sed multum

Programming Question - Compute GCD

Part1: write a function that takes two integers as input and returns their gcd using the famous Euclidean algorithm.

Solutions:

Solution part 1:

Solution part 2:

Join the Discussion Cancel reply