Greatest Common Divider

Wiki

EPI 25.1

Description:

Example:

GCD of 98 and 56 is 14

GCD of 8 and 4 is 4

Idea:

Method 1, time worst O(n)

a, b both >= 0

gcd(a,b) = a, if a==b
gcd(a,b) = gcd(a-b, b) if a>b
gcd(a,b) = gcd(a, b-a) if a<b

Method 2, time O(log(a+b)) = O(logn)

gcd(a, 0) = a
gcd(a, b) = gcd(b, a%b)

Method 3, Binary search O(loga+logb)

def gcd(a, b, res):
    if a == b:
        return res * a
    elif (a % 2 == 0) and (b % 2 == 0):
        return gcd(a // 2, b // 2, 2 * res)
    elif (a % 2 == 0):
        return gcd(a // 2, b, res)
    elif (b % 2 == 0):
        return gcd(a, b // 2, res)
    elif a > b:
        return gcd(a - b, b, res)
    else:
        return gcd(a, b - a, res

Code:

#include <iostream>
#include <vector>
using namespace std;

// Method 1
int gcdSubtract(int a, int b){
    if(a==b) return a;
    if(a>b) return gcdSubtract(a-b, b);
    if(a<b) return gcdSubtract(a, b-a);
}

// Method 2
int gcdDivide(int a, int b){
    if(b==0) return a;
    return gcdDivide(b, a%b);
}

int main(){
    cout<<gcdSubtract(98, 56)<<' '<<gcdSubtract(56, 98)<<endl;
    cout<<gcdDivide(98, 56)<<' '<<gcdDivide(56, 98)<<endl;
}