GCD of Two Numbers

Easy

Given two positive integers a and b, find GCD of a and b.

Note: Don't use the inbuilt gcd function

Example 1

Input

a = 20, b = 28

Output

Explanation

GCD of 20 and 28 is 4

Example 2

Input

a = 60, b = 36

Output

Explanation

GCD of 60 and 36 is 12

Constraints

1 ≤ a ≤ 10^9

1 ≤ b ≤ 10^9

Hints:

Hint 1

Start with the straightforward approach, then optimize time or space if needed.

Author & Technical Reviewer

Technically reviewed by: ExamAdda Technical Review Team

Technical Reviewers, ExamAdda

Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.

Published

Jul 20, 2026

Last updated

Aug 6, 2026

Content Verification Methodology

Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.

Report a correction:editorial@examadda.org

Auto

Loading editor...

Input

Expected Output