C++ में बड़ी संख्या को समान योग वाले खंडों में विभाजित करें

समस्या विवरण

जांचें कि क्या एक बड़ी संख्या (स्ट्रिंग के रूप में) को दो या अधिक खंडों में बांटा जा सकता है जिनके अंकों का योग समान हो।

उदाहरण: "74325" → (7), (4,3), (2,5) → सभी का योग 7

एल्गोरिदम

1. प्रीफिक्स योग सरणी बनाएं
2. प्रत्येक संभावित पहले खंड के लिए (0 से i-1)
3. शेष स्ट्रिंग को समान योग वाले खंडों में बांटने का प्रयास करें
4. यदि अंत तक सफलतापूर्वक बंट जाए → true

उदाहरण कोड

#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, 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, can be segmented into more than two segments";
    else
        cout << "No, cannot be segmented";
    return 0;
}

आउटपुट

Yes, This can be segmented into more than two segments