GCD Or HCF
Basic Maths DSA practice problem on Onlearn.
Difficulty: easy.
Topics: Find the Greatest Common Divisor (GCD) of Two Integers, Greatest Common Divisor (GCD), Euclidean Algorithm, Mathematical Algorithms, Time Complexity, Space Complexity, Loops, Conditional Statements, Basic Arithmetic, brute force, mathematical operations, optimization, time complexity analysis, number theory algorithms, number theory, GCD (Euclidean Algorithm), Brute-Force Search, Divisors & Factors, Problem Solving Techniques, Modular Arithmetic.
Greatest Common Divisor Problem Statement Given two non negative integers N1 and N2, find their Greatest Common Divisor (GCD). The Greatest Common Divisor of any two integers is the largest positive integer that divides both numbers without leaving a remainder. Input Specification Two integers, N1 and N2. Output Specification An integer representing the GCD of N1 and N2. Sample Test Cases Example 1: Input: Output: Explanation: Factors of 9: 1, 3, 9. Factors of 12: 1, 2, 3, 4, 6, 12. Common Factors: 1, 3. The greatest among these is 3. Example 2: Input: Output: Explanation: Factors of 20: 1, 2, 4, 5, 10, 20. Factors of 15: 1, 3, 5, 15. Common Factors: 1, 5. The greatest among these is 5.