परिचय
इस ट्यूटोरियल में हमें यह जांचना है कि 1 से n तक की प्राकृतिक संख्याओं को दो हिस्सों में विभाजित किया जा सकता है या नहीं। इसे निम्नलिखित शर्तों को पूरा करना होगा:
- दोनों श्रृंखलाओं के योग का निरपेक्ष अंतर m होना चाहिए।
- और दोनों योगों का GCD 1 होना चाहिए यानी वे को-प्राइम (co-prime) हों।
पहली n प्राकृतिक संख्याओं का योग (n*(n+1))/2 होता है। हम sumOne और sumTwo ढूंढ सकते हैं क्योंकि हमारे पास कुल योग और अंतर m है। समीकरण देखें:
sumOne + sumTwo = (n*(n+1))/2 sumOne - sumTwo = m
उदाहरण
जांचें कि निरपेक्ष योग m के बराबर है या नहीं। फिर GCD के लिए जांचें।
#include <bits/stdc++.h>
using namespace std;
bool canSplitIntoTwoHalves(int n, int m) {
int total_sum = (n * (n + 1)) / 2;
int sumOne = (total_sum + m) / 2;
int sumTwo = total_sum - sumOne;
if (total_sum < m) {
return false;
}
if (sumOne + sumTwo == total_sum && sumOne - sumTwo == m) {
return (__gcd(sumOne, sumTwo) == 1);
}
return false;
}
int main() {
int n = 10, m = 17;
if (canSplitIntoTwoHalves(n, m)) {
cout << "Can split";
} else {
cout << "Can't split";
}
return 0;
}
आउटपुट
Can split
निष्कर्ष
n=10 और m=17 के लिए, कुल योग 55 है। sumOne = 36, sumTwo = 19। अंतर 17 है और GCD(36,19) = 1, इसलिए विभाजन संभव है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।