Compute GCD With Tests | Dataford Interview Questions

HackerEarth assessment inputs may contain integers larger than Python's native integer limits in restricted environments. Given two signed integers as decimal strings, compute their greatest common divisor without converting either entire input to a built-in integer.

Use Euclid's algorithm, where gcd(a, b) = gcd(b, a mod b), and implement decimal remainder arithmetic on strings.

Formal Specification

Implement gcd_huge(a, b).

Input: Two strings a and b, each representing a signed base-10 integer.
Output: A string representing the non-negative greatest common divisor.
Leading zeroes may appear in either input. If both values are zero, return "0".

Constraints

1 <= len(a), len(b) <= 100000
Each input contains an optional leading '+' or '-' followed by decimal digits
At least one digit follows any sign
Do not convert the complete input strings to built-in integers
Return a canonical non-negative decimal string

Function Signature

def gcd_huge(a, b):

Your question is Compute GCD With Tests. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem