Compute GCD With Tests

HardPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Compute GCD With Tests. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

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 solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output