समस्या
सीमा से कम धनात्मक पूर्णांकों पर विचार करें। किसी मान को शामिल करें यदि वह कम से कम एक गैर-शून्य गुणजक से विभाजित होता है। यदि किसी मान को कई गुणजक विभाजित करते हैं, तो भी उसे केवल एक बार गिनें। शून्य गुणजकों की अनदेखी करें। गुणजक [3, 5] देने पर यह 3 या 5 के गुणजकों का परिचित कार्य बन जाता है।
sum_of_multiples(limit, factors) को लागू करें।
इनपुट
limit: विशिष्ट ऊपरी सीमा।
factors: वे गुणजक जिनके गुणजक योग्य हैं।
आउटपुट
योग्य और अलग-अलग धनात्मक पूर्णांकों का योग लौटाएँ।
सीमाएँ
0 ≤ limit ≤ 100,000। गुणजकों की संख्या 0 से 20 तक हो सकती है, प्रत्येक 0 से 100,000 के बीच। गुणजकों में पुनरावृत्ति (डुप्लिकेट) हो सकती है।
उदाहरण
इनपुट:
limit = 12
factors = [3, 5]
अपेक्षित आउटपुट:
expected = 33इनपुट:
long long limit = 12;
std::vector<long long> factors = {3, 5};
अपेक्षित आउटपुट:
long long expected = 33;इनपुट:
long limit = 12;
long[] factors = new long[] {3, 5};
अपेक्षित आउटपुट:
long expected = 33;व्याख्या
शामिल मान हैं 3, 5, 6, 9, और 10। इनका योग 33 है।
इनपुट:
limit = 10
factors = [2, 4]
अपेक्षित आउटपुट:
expected = 20इनपुट:
long long limit = 10;
std::vector<long long> factors = {2, 4};
अपेक्षित आउटपुट:
long long expected = 20;इनपुट:
long limit = 10;
long[] factors = new long[] {2, 4};
अपेक्षित आउटपुट:
long expected = 20;व्याख्या
2, 4, 6, और 8 को शामिल करें। मान 4 और 8 दोनों गुणजकों से मेल खाने के बावजूद केवल एक बार गिने जाते हैं।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
सिर्फ वे values जो कम-से-कम एक usable factor से divisible हैं, एक बार contribute करें.
संकेत 2
Overlapping factor multiples को बिना double counting के combine करने के लिए inclusion-exclusion use करो.
संकेत 3
कोई arithmetic करने से पहले zero factors और duplicates ignore करो.
अपेक्षित जटिलता
समय O(2^m), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।