यहां हम एक प्रोग्राम देखेंगे, जो यह जांच सकता है कि क्या किसी संख्या को बराबर योग के साथ एक से अधिक खंडों में विभाजित किया जा सकता है। मान लीजिए कि कोई संख्या 74325 के समान है, तो इसे तीन भागों (7), (4, 3), (2, 5) में विभाजित किया जा सकता है, सभी समान मान के हैं।
इस समस्या को हल करने के लिए हमें इन चरणों का पालन करना होगा।
- संख्या को स्ट्रिंग के रूप में लें
- सरणी का उपसर्ग योग रखने के लिए सरणी का उपयोग करें
- अब दूसरे एलिमेंट से लास्ट एलिमेंट तक जा रहे हैं, और पहला सेगमेंट 0 से i-1 तक होगा, जिसका योग prefix_sum[i - 1] पर रखा जाएगा
- एक अन्य चर का उपयोग करें जो 1 से n तक जाता है, फिर योग जोड़ते रहें।
- यदि योग मान किसी भी स्तर पर उपसर्ग_योग [i - 1] के समान है, तो खंड का योग पहले के बराबर है।
- सेगमेंट योग मान को 0 के रूप में इनिशियलाइज़ करें, फिर पॉइंटर को मूव करते रहें।
- यदि किसी भी स्तर पर खंड योग उपसर्ग_योग [i - 1] से अधिक है तो लूप को तोड़ दें
- यदि हम अंतिम गंतव्य पर पहुँचते हैं, और यदि अंतिम खंड का योग पहले खंड के योग के समान है, तो इसे समान योग के खंडों में विभाजित किया जा सकता है।
उदाहरण
#include <iostream>
using namespace std;
bool canBeSegmented(string str) {
int n = str.length();
int prefix_sum[n];
prefix_sum[0] = str[0] - '0';
for (int i = 1; i < n; i++) {
prefix_sum[i] = prefix_sum[i - 1] + (str[i] - '0');
}
for (int i = 1; i <= n - 1; i++) {
int sum = prefix_sum[i - 1];
int prev_sum = 0;
int it = i;
bool flag = false;
while (it < n) {
prev_sum += str[it] - '0';
if (prev_sum == sum) {
prev_sum = 0;
flag = true;
} else if (prev_sum > sum) {
break;
}
it++;
}
if (prev_sum == 0 && it == n && flag) {
return true;
}
}
return false;
}
int main() {
string s = "74325";
if (canBeSegmented(s))
cout << "Yes, This can be segmented into more than two segments";
else
cout << "No, This can not be segmented into more than two segments";
} आउटपुट
Yes, This can be segmented into more than two segments