GCD (Euclidean)

Category: Math & Number Theory

Difficulty: beginner

Description: Euclid's algorithm for GCD

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

Space Complexity: O(1)

Related LeetCode Problems

• 1071. Greatest Common Divisor of Strings (Easy)
• 1979. Find Greatest Common Divisor of Array (Easy)
• 1250. Check If It Is a Good Array (Medium)
• 2654. Minimum Number of Operations to Make All Array Elements Equal to 1 (Medium)
• 1998. GCD Sort of an Array (Medium)
• 1146. Snapshot Array (related arithmetic / structure practice) (Medium)
• 2149. Rearrange Array Elements by Sign (related practice) (Easy)
• 2269. Find the K-Beauty of a Number (related divisibility practice) (Easy)
• 325. Maximum Size Subarray Sum Equals k (related number-theory practice) (Medium)
• 1790. Check if One String Swap Can Make Strings Equal (auxiliary string/number practice) (Easy)