समस्या
Return the greatest common divisor of a and b. Euclid's algorithm repeatedly replaces (a, b) with (b, a mod b) until b is 0.
Implement gcd(a, b).
Input
a: The first number. b: The second number.
Output
Return gcd(a, b). gcd(0, 0) is 0.
सीमाएँ
0 ≤ a, b ≤ 10¹⁸
उदाहरण
उदाहरण 1
इनपुट:
a = 48
b = 18
अपेक्षित आउटपुट:
expected = 6इनपुट:
long long a = 48;
long long b = 18;
अपेक्षित आउटपुट:
long long expected = 6;इनपुट:
long a = 48;
long b = 18;
अपेक्षित आउटपुट:
long expected = 6;व्याख्या
48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, so the answer is 6.
उदाहरण 2
इनपुट:
a = 17
b = 5
अपेक्षित आउटपुट:
expected = 1इनपुट:
long long a = 17;
long long b = 5;
अपेक्षित आउटपुट:
long long expected = 1;इनपुट:
long a = 17;
long b = 5;
अपेक्षित आउटपुट:
long expected = 1;व्याख्या
17 and 5 share no factor other than 1.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
The gcd does not change when you replace a pair with the remainder step.
संकेत 2
Keep swapping the roles of the two numbers until the second becomes zero.
संकेत 3
Be sure to handle the case where both inputs are zero.
अपेक्षित जटिलता
O(log min(a, b)) time, O(1) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।