33.Euclid’s GCD: The Only Method You Need (Python)

Learn how to compute the Greatest Common Divisor (GCD) of two numbers using the Euclidean Algorithm in Python. We cover intuition, step-by-step walkthrough, and a clean function you can reuse in interviews and projects. Examples: GCD(48, 18) = 6, GCD(270, 192) = 6. def gcd(a, b): # Step 1: Keep looping until the second number becomes zero # (This means we have found the GCD) while b != 0: # Step 2: Replace (a, b) with (b, a % b) # Example: gcd(48, 18) # a = 48, b = 18 → new (a, b) = (18, 48 % 18) = (18, 12) # a = 18, b = 12 → new (a, b) = (12, 18 % 12) = (12, 6) # a = 12, b = 6 → new (a, b) = (6, 12 % 6) = (6, 0) # Now b = 0, so loop stops a, b = b, a % b # Step 3: When b becomes 0, the current value of 'a' is the GCD return a #Python #CodingInterview #Algorithms #Math #EuclideanAlgorithm