How it works:

The Euclidean algorithm finds the Greatest Common Divisor (GCD) by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller until one becomes zero.

• Time Complexity : O(Log (min(a, b)))
• Auxiliary Space : O(Log (min(a, b)))