GCD of two number

Example 1:

Input: 10,25
Output: 5                                                                                                     

Approach: Euclidean algorithm

Java

public class GCD {

    public static void main(String[] args) {

        int a = 15;

        int b = 30;

        int gcd = gretestCommonDivisor(a, b);

        System.out.println("GCD is " + gcd);

    }

    private static int gretestCommonDivisor(int a, int b) {

        if (b == 0)

            return a;

        return gretestCommonDivisor(b, a % b);

    }

}

//Time Complexity: O(log(min(a,b)))

C++

#include <bits/stdc++.h>

using namespace std;

//Function to find GCD of two numbers

int gretestCommonDivisor(int a,int b)

{

    //Base case

    if(b==0)

       return a;

    return gretestCommonDivisor(b,a%b);

}

int main()

{

    int a=10,b=25;

    int gcd=gretestCommonDivisor(a,b);

    cout<<"GCD is "<<gcd<<"\n";

    return 0;

}

//Time Complexity: O(log(min(a,b)))