इस समस्या में, हमें तीन पूर्णांक M1, M2, और N दिए गए हैं। हमारा कार्य N से नीचे दो संख्याओं के गुणकों का योग ढूंढने के लिए एक प्रोग्राम बनाना है।
यहां, हम N से नीचे उन सभी तत्वों को जोड़ेंगे जो M1 या M2 के गुणक हैं।
आइए एक उदाहरण लेकर समस्या को समझते हैं,
इनपुट
N = 13, M1 = 4, M2 = 6
आउटपुट
20
व्याख्या - 4 और 6 के गुणक जो 13 से कम हैं: 4, 6, 8, 12।
समस्या का एक सरल समाधान 1 से N तक लूप करना और उन सभी मानों को जोड़ना है जो M1 या M2 से विभाज्य हो सकते हैं।
एल्गोरिदम
चरण 1 - योग = 0, i = 0। i = 1 से N तक लूप करें।
चरण 1.1 - यदि (i%M1 == 0) या (i%M2 == 0), योग += i
चरण 2 - योग लौटाएं।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
#include <iostream>
using namespace std;
int calcMulSum(int N, int M1, int M2) {
int sum = 0;
for (int i = 0; i < N; i++)
if (i % M1 == 0 || i % M2 == 0)
sum += i;
return sum;
}
int main() {
int N = 24, M1 = 4, M2 = 7;
cout << " " << M1 << " और " << M2 << " के गुणकों का योग " << N << " से नीचे है: " << calcMulSum(N, M1, M2);
return 0;
}
आउटपुट
4 और 7 के गुणकों का योग 24 से नीचे है: 102
यह हमारे समस्या का सबसे अच्छा समाधान नहीं है क्योंकि यह O(n) समय जटिलता लेता है।
एक बेहतर समाधान श्रृंखला के योग के लिए गणितीय सूत्रों का उपयोग करना होगा।
यहां, हम श्रृंखला के योग के सूत्र का उपयोग करेंगे। अंतिम योग (M1 के गुणक + M2 के गुणक - M1*M2 के गुणक) होगा।
n पदों तक x के गुणक का योग दिया जाता है,
Sum(X) = (n * (1+n) * X)/2
आइए योग को सूत्रबद्ध करें,
sum = ( ( ((n/M1)*(1+(n/M1))*M1)/2) + ((n/M2)*(1+(n/M2))*M2)/2 ) - ((n/(M1*M2))*(1+(n/(M1*M2)))*M1*M2)/2 ) )
उदाहरण
समाधान को दर्शाने वाला प्रोग्राम,
#include <iostream>
using namespace std;
int calcMulSum(int N, int M1, int M2) {
N--;
return (((N/M1) * (1 + (N/M1)) * M1 / 2) + ((N/M2) * (1 + (N/M2)) * M2 / 2) - ((N/(M1*M2)) * (1 + (N/(M1*M2))) * (M1*M2) / 2));
}
int main() {
int N = 24, M1 = 4, M2 = 7;
cout << " " << M1 << " और " << M2 << " के गुणकों का योग " << N << " से नीचे है: " << calcMulSum(N, M1, M2);
return 0;
}
आउटपुट
4 और 7 के गुणकों का योग 24 से नीचे है: 102
