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

DZone's Guide to

# GCD: Divide Et Impera

·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views
```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:

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Opinions expressed by DZone contributors are their own.