समस्या
Return the least common multiple of a and b, the smallest positive number that both divide. lcm(a, b) = a / gcd(a, b) × b.
Implement lcm(a, b).
Input
a: The first positive number. b: The second positive number.
Output
Return 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;व्याख्या
Multiples of 4: 4, 8, 12…; multiples of 6: 6, 12…; the first common one is 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;व्याख्या
A number's LCM with itself is the number: 7.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Use the relationship between gcd and lcm instead of searching for multiples.
संकेत 2
Compute the gcd first, then combine the two numbers carefully.
संकेत 3
Divide before multiplying to reduce overflow risk, even with large inputs.
अपेक्षित जटिलता
O(log min(a, b)) time, O(1) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।