इस समस्या में, हमने तीन पूर्णांक 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<<"The sum of multiples of "<<M1<<" and "<<M2<<" below "<<N<<" is "<<calcMulSum(N, M1, M2);
return 0;
} आउटपुट
The sum of multiples of 4 and 7 below 24 is 102
यह हमारी समस्या का सबसे अच्छा समाधान नहीं है क्योंकि इसमें O(n) समय जटिलता लगती है।
श्रृंखला के योग के लिए गणितीय सूत्रों का उपयोग करना एक बेहतर समाधान होगा।
यहां, हम श्रृंखला के योग के लिए सूत्र का उपयोग करेंगे। अंतिम योग होगा (M1 का गुणज + M2 का गुणज - M1*M2 का गुणज)
x से n पदों तक के गुणजों का योग निम्न द्वारा दिया जाता है,
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<<"The sum of multiples of "<<M1<<" and "<<M2<<" below "<<N<<" is "<<calcMulSum(N, M1, M2);
return 0;
} आउटपुट
The sum of multiples of 4 and 7 below 24 is 102