समस्या
एक बेकरी बिस्कुट lo से hi तक हर साइज़ के डिब्बों में पैक करती है। वह एक बार में इतने बिस्कुट बनाना चाहती है कि इनमें से किसी भी साइज़ के डिब्बे पूरे भर जाएँ और एक भी बिस्कुट न बचे। उत्तर वह सबसे छोटी धनात्मक संख्या है जो lo से hi तक के हर पूर्णांक से विभाज्य हो, यानी इन सबका लघुत्तम समापवर्त्य (LCM)।
smallest_multiple(lo, hi) लिखिए।
इनपुट
lo: डिब्बे का सबसे छोटा साइज़।
hi: डिब्बे का सबसे बड़ा साइज़।
आउटपुट
वह सबसे छोटा धनात्मक पूर्णांक लौटाइए जिसे lo, lo + 1, ..., hi में से हर संख्या बिना शेषफल के विभाजित करे।
सीमाएँ
1 ≤ lo ≤ hi ≤ 40 (उत्तर signed 64-bit पूर्णांक में समा जाता है)
उदाहरण
इनपुट:
lo = 1
hi = 6
अपेक्षित आउटपुट:
expected = 60
इनपुट:
long long lo = 1;
long long hi = 6;
अपेक्षित आउटपुट:
long long expected = 60;
इनपुट:
long lo = 1;
long hi = 6;
अपेक्षित आउटपुट:
long expected = 60;
व्याख्या
60 संख्याओं 1, 2, 3, 4, 5 और 6 से विभाज्य है, और इससे छोटी कोई धनात्मक संख्या नहीं, इसलिए उत्तर 60 है।
इनपुट:
lo = 4
hi = 6
अपेक्षित आउटपुट:
expected = 60
इनपुट:
long long lo = 4;
long long hi = 6;
अपेक्षित आउटपुट:
long long expected = 60;
इनपुट:
long lo = 4;
long hi = 6;
अपेक्षित आउटपुट:
long expected = 60;
व्याख्या
lcm(4, 5) = 20 और lcm(20, 6) = 60, इसलिए उत्तर फिर से 60 है: छोटे साइज़ों से कुछ नहीं बदला।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
पूरी रेंज का lcm एक-एक संख्या लेकर बनाया जा सकता है।
संकेत 2
lcm(a, b) = a / gcd(a, b) × b।
संकेत 3
गुणा करने से पहले भाग दीजिए, ताकि बीच का मान कभी उत्तर से बड़ा न हो।
अपेक्षित जटिलता
समय O(n log M), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।