समस्या
a और b का महत्तम समापवर्तक (GCD) लौटाएँ। यूक्लिड की विधि में (a, b) को बार-बार (b, a mod b) से बदलते हैं जब तक b शून्य न हो जाए।
gcd(a, b) को लागू करें।
इनपुट
a: पहला संख्या। b: दूसरा संख्या।
आउटपुट
gcd(a, b) लौटाएँ। gcd(0, 0) का मान 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, इसलिए उत्तर 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 और 5 के बीच 1 के अलावा कोई समान गुणनखंड नहीं है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
gcd तब नहीं बदलता जब pair को remainder step से replace करते हैं.
संकेत 2
दोनों numbers की roles बदलते रहें जब तक second zero न हो जाए.
संकेत 3
ध्यान रखें कि दोनों inputs zero हों तो case handle करें.
अपेक्षित जटिलता
समय O(log min(a, b)), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।