Euclid’s algorithm is used to find GCD of two numbers.
There are mainly two versions of algorithm.
Version 1 (Using subtraction)
C++
// Recursive function to return gcd of a and bint gcd(int a, int b){ if (a == b) return a; return (a > b) ? gcd(a - b, b) : gcd(a, b - a);} |
C
// Recursive function to return gcd of a and bint gcd(int a, int b){ if (a == b) return a; return (a > b)? gcd(a-b, b): gcd(a, b-a);} |
Java
// Recursive function to return gcd of a and bstatic int gcd(int a, int b){ if (a == b) return a; return (a > b) ? gcd(a - b, b) : gcd(a, b - a);}// This code is contributed by subham348. |
Python3
# Recursive function to return gcd of a and bdef gcd(a, b): if (a == b): return a return gcd(a-b, b) if (a > b) else gcd(a, b-a) # This code is contributed by subham348. |
C#
// Recursive function to return gcd of a and bstatic int gcd(int a, int b){ if (a == b) return a; return (a > b) ? gcd(a - b, b) : gcd(a, b - a);}// This code is contributed by subham348. |
Javascript
// Recursive function to return gcd of a and bfunction gcd(a, b){ if (a === b) return a; return (a > b)? gcd(a-b, b): gcd(a, b-a);}// This code is contributed by subham348. |
Time Complexity: O(max(a, b))
Auxiliary Space: O(1)
Version 2 (Using modulo operator)
C++
// Function to return gcd of a and bstatic int gcd(int a, int b){ if (a == 0) return b; return gcd(b % a, a);} |
C
// Function to return gcd of a and bint gcd(int a, int b){ if (a == 0) return b; return gcd(b%a, a);} |
Java
// Function to return gcd of a and bstatic int gcd(int a, int b){ if (a == 0) return b; return gcd(b%a, a);}// This code is contributed by subham348. |
C#
// Function to return gcd of a and bstatic int gcd(int a, int b){ if (a == 0) return b; return gcd(b%a, a);}// This code is contributed by subham348. |
Javascript
// Function to return gcd of a and bfunction gcd(a, b){ if (a === 0) return b; return gcd(b%a, a);}// This code is contributed by subham348. |
Python3
# Python3 Function to return gcd of a and bdef gcd(a, b): if (a == 0): return b return gcd(b % a, a)# This code is contributed by phasing17 |
Time Complexity: O(log(max(a, b)))
Auxiliary Space: O(1)
Which of the above two is more efficient?
Version 1 can take linear time to find the GCD, consider the situation when one of the given numbers is much bigger than the other. Version 2 is obviously more efficient as there are less recursive calls and takes logarithmic time.
Consider a situation where modulo operator is not allowed, can we optimize version 1 to work faster?
Below are some important observations. The idea is to use bitwise operators. We can find x/2 using x>>1. We can check whether x is odd or even using x&1.
gcd(a, b) = 2*gcd(a/2, b/2) if both a and b are even.
gcd(a, b) = gcd(a/2, b) if a is even and b is odd.
gcd(a, b) = gcd(a, b/2) if a is odd and b is even.
Below is C++ implementation.
C++
// Efficient C++ program when % and / are not allowedint gcd(int a, int b){ // Base cases if (b == 0 || a == b) return a; if (a == 0) return b; // If both a and b are even, divide both a // and b by 2. And multiply the result with 2 if ((a & 1) == 0 && (b & 1) == 0) return gcd(a >> 1, b >> 1) << 1; // If a is even and b is odd, divide a by 2 if ((a & 1) == 0 && (b & 1) != 0) return gcd(a >> 1, b); // If a is odd and b is even, divide b by 2 if ((a & 1) != 0 && (b & 1) == 0) return gcd(a, b >> 1); // If both are odd, then apply normal subtraction // algorithm. Note that odd-odd case always // converts odd-even case after one recursion return (a > b) ? gcd(a - b, b) : gcd(a, b - a);} |
C
// Efficient C++ program when % and / are not allowedint gcd(int a, int b){ // Base cases if (b == 0 || a == b) return a; if (a == 0) return b; // If both a and b are even, divide both a // and b by 2. And multiply the result with 2 if ( (a & 1) == 0 && (b & 1) == 0 ) return gcd(a>>1, b>>1) << 1; // If a is even and b is odd, divide a by 2 if ( (a & 1) == 0 && (b & 1) != 0 ) return gcd(a>>1, b); // If a is odd and b is even, divide b by 2 if ( (a & 1) != 0 && (b & 1) == 0 ) return gcd(a, b>>1); // If both are odd, then apply normal subtraction // algorithm. Note that odd-odd case always // converts odd-even case after one recursion return (a > b)? gcd(a-b, b): gcd(a, b-a);} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG { static int gcd(int a, int b) { // Base cases if (b == 0 || a == b) return a; if (a == 0) return b; // If both a and b are even, divide both a // and b by 2. And multiply the result with 2 if ((a & 1) == 0 && (b & 1) == 0) return gcd(a >> 1, b >> 1) << 1; // If a is even and b is odd, divide a by 2 if ((a & 1) == 0 && (b & 1) != 0) return gcd(a >> 1, b); // If a is odd and b is even, divide b by 2 if ((a & 1) != 0 && (b & 1) == 0) return gcd(a, b >> 1); // If both are odd, then apply normal subtraction // algorithm. Note that odd-odd case always // converts odd-even case after one recursion return (a > b) ? gcd(a - b, b) : gcd(a, b - a); } // Driver Code public static void main(String[] args) { System.out.println(gcd(54, 36)); }}// This code is contributed by phasing17 |
Python3
def gcd(a, b): # Base cases if (b == 0 or a == b): return a if (a == 0): return b # If both a and b are even, divide both a and b by 2. # And multiply the result with 2 if ((a & 1) == 0 and (b & 1) == 0): return gcd(a >> 1, b >> 1) * 2 # If a is even and b is odd, divide a by 2 if ((a & 1) == 0 and (b & 1) != 0): return gcd(a >> 1, b) # If a is odd and b is even, divide b by 2 if ((a & 1) != 0 and (b & 1) == 0): return gcd(a, b >> 1) # If both are odd, then apply normal subtraction algorithm. # Note that odd-odd case always converts odd-even case after one recursion return gcd(a-b, b) if a > b else gcd(a, b-a)# This code is contributed by Vikram_Shirsat |
C#
// C# program to implement// the above approachusing System;class GFG{ // Efficient C++ program when % and / are not allowed int gcd(int a, int b) { // Base cases if (b == 0 || a == b) return a; if (a == 0) return b; // If both a and b are even, divide both a // and b by 2. And multiply the result with 2 if ( (a & 1) == 0 && (b & 1) == 0 ) return gcd(a>>1, b>>1) << 1; // If a is even and b is odd, divide a by 2 if ( (a & 1) == 0 && (b & 1) != 0 ) return gcd(a>>1, b); // If a is odd and b is even, divide b by 2 if ( (a & 1) != 0 && (b & 1) == 0 ) return gcd(a, b>>1); // If both are odd, then apply normal subtraction // algorithm. Note that odd-odd case always // converts odd-even case after one recursion return (a > b)? gcd(a-b, b): gcd(a, b-a); }}// This code is contributed by code_hunt. |
Javascript
// Efficient JavaScript program when % and / are not allowedfunction gcd(a, b){ // Base cases if (b == 0 || a == b) return a; if (a == 0) return b; // If both a and b are even, divide both a // and b by 2. And multiply the result with 2 if ( (a & 1) == 0 && (b & 1) == 0 ) return gcd(a>>1, b>>1) << 1; // If a is even and b is odd, divide a by 2 if ( (a & 1) == 0 && (b & 1) != 0 ) return gcd(a>>1, b); // If a is odd and b is even, divide b by 2 if ( (a & 1) != 0 && (b & 1) == 0 ) return gcd(a, b>>1); // If both are odd, then apply normal subtraction // algorithm. Note that odd-odd case always // converts odd-even case after one recursion return (a > b)? gcd(a-b, b): gcd(a, b-a);}// This code is contributed by phasing17 |
Time Complexity: O(log(max(a, b)))
Auxiliary Space: O(1)
This article is compiled by Shivam Agrawal. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
