//Basic Euclidean Algorithm for GCD 
//The algorithm is based on the below facts. 

//1. If we subtract a smaller number from a larger one (we reduce a larger number), GCD doesn’t change. 
// So if we keep subtracting repeatedly the larger of two, we end up with GCD.
//2. Now instead of subtraction, if we divide the smaller number, the algorithm stops when we find the remainder 0.

public static int gcd(int a, int b){
        if (a == 0) return b;
        return gcd(b%a, a);
}

// Time Complexity: O(Log max(a, b))