Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

GCD: Divide Et Impera

DZone's Guide to

GCD: Divide Et Impera

·
Free Resource
Calculates the Greatest Common Denominator (GCD) of an array of ints using a Divide at Impera approach.

Time: O(lg(n))
Memory: O(n)


#include 
  
   

int gcd(int a, int b) {
	int r = a % b;
	while (r) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

int gcdv(int *v, int p, int r) {
	if (r == p + 1) {
		//printf("%d,%d: %d\n", p, r, gcd(v[p], v[r]));
		return gcd(v[p], v[r]);
	}
	
	if (r == p) {
		//printf("%d: %d\n", r, v[r]);
		return v[p];
	}
	
	int q = (p + r) / 2;
	//printf("%d,%d: %d\n", p, r, gcd(gcdv(v, p, q), gcdv(v, q + 1, r)));
	return gcd(gcdv(v, p, q), gcdv(v, q + 1, r));
}

int main(int argc, char *argv[]) {
	int v[] = {45, 60, 125, 345, 65, 9875, 4555};
	
	printf("GCD: %d\n", gcdv(v, 0, 6));
	
	return 0;
}


  
Topics:

Opinions expressed by DZone contributors are their own.

The best of DZone straight to your inbox.

SEE AN EXAMPLE
Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.
Subscribe

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}