समस्या
a और b का लघुत्तम समापवर्त्य (LCM) लौटाएँ, यानी वह सबसे छोटी धनात्मक संख्या जिसे दोनों विभाजित करते हैं। lcm(a, b) = a / gcd(a, b) × b।
lcm(a, b) को लागू करें।
इनपुट
a: पहला धनात्मक संख्या। b: दूसरा धनात्मक संख्या।
आउटपुट
lcm(a, b) लौटाएँ।
सीमाएँ
1 ≤ a, b ≤ 1,000,000,000
उदाहरण
इनपुट:
a = 4
b = 6
अपेक्षित आउटपुट:
expected = 12इनपुट:
long long a = 4;
long long b = 6;
अपेक्षित आउटपुट:
long long expected = 12;इनपुट:
long a = 4;
long b = 6;
अपेक्षित आउटपुट:
long expected = 12;व्याख्या
4 के गुणज: 4, 8, 12…; 6 के गुणज: 6, 12…; पहला समान गुणज 12 है।
इनपुट:
a = 7
b = 7
अपेक्षित आउटपुट:
expected = 7इनपुट:
long long a = 7;
long long b = 7;
अपेक्षित आउटपुट:
long long expected = 7;इनपुट:
long a = 7;
long b = 7;
अपेक्षित आउटपुट:
long expected = 7;व्याख्या
किसी संख्या का स्वयं के साथ LCM वही संख्या होती है: 7।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Multiples search करने के बजाय gcd और lcm के relation का use करें.
संकेत 2
पहले gcd compute करें, फिर दोनों numbers को carefully combine करें.
संकेत 3
Overflow risk कम करने के लिए multiply से पहले divide करें, बड़े inputs पर भी.
अपेक्षित जटिलता
समय O(log min(a, b)), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।