Compute HCF or GCD of two numbers using Command Line Arguments
Filed under TCS
Free read 2 of 3The question
Implement a program to compute the Greatest Common Divisor (GCD) or Highest Common Factor (HCF) of two integers using the Euclidean algorithm. The inputs are typically provided as command-line arguments.
Constraints
- Inputs are non-negative integers
- Handle cases where one of the inputs is zero
- Efficiently handle large integers up to 10^9
Examples
- Input
- 48, 18
- Output
- 6
- Why
- 48 = 18*2 + 12; 18 = 12*1 + 6; 12 = 6*2 + 0. The last non-zero remainder is 6.
Approach
Convert command line string arguments into integers.
Repeatedly replace the larger number with its remainder when divided by the smaller number.
When the remainder becomes zero, the current divisor is the GCD.
Use an iterative approach to avoid recursion depth issues in some languages.
Solution
O(log(min(a, b))) time, O(1) space
class Solution:
def get_gcd(self, a: int, b: int) -> int:
# Iterative Euclidean Algorithm
while b:
a, b = b, a % b
return a
Tips
- What they are testing: Test with prime numbers, identical numbers, and cases where one number is 1.
- Common mistake: Forgetting that GCD(0, x) is x; the algorithm must not divide by zero.
Related TCS questions
Collected from public candidate posts and coding forums. Updated Nov 2026.