C++ में संख्या के संभावित कट्स ताकि अधिकतम भाग 3 से विभाज्य हों

इस समस्या में, हमें एक बड़ी पूर्णांक मान (10⁵ अंकों तक) दिया गया है। हमारा कार्य कट्स की कुल संख्या प्रिंट करना है ताकि अधिकतम भाग 3 से विभाज्य हों।

समस्या को समझने के लिए एक उदाहरण लेते हैं

इनपुट - 9216

आउटपुट - 3

व्याख्या - संख्या को 9|21|6 के रूप में विभाजित किया गया है।

इस समस्या को हल करने के लिए, हमें संख्या के कम से कम महत्वपूर्ण बिट से शुरू करना होगा यानी संख्या का अंतिम अंक। यहां, हम 3 से विभाज्य सबसे छोटी संख्या ढूंढेंगे। और फिर इसके आधार पर काउंट अपडेट करेंगे।

उदाहरण - यदि arr[i] 3 से विभाज्य संख्या बनाता है, तो हम काउंट बढ़ाएंगे और संख्या के अगले अंक पर जाएंगे। यदि arr[i] 3 से विभाज्य नहीं है, तो हम इसे अगले अंक के साथ जोड़ेंगे और 3 की विभाज्यता की जांच करेंगे।

3 की विभाज्यता - एक संख्या 3 से विभाज्य होती है यदि संख्या के अंकों का योग 3 से विभाज्य होता है।

उदाहरण

हमारे समाधान के कार्यान्वयन को दर्शाने वाला प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

int countMaximum3DivisibleNumbers(string number) {
    int n = number.length();
    vector<int> remIndex(3, -1);
    remIndex[0] = 0;
    vector<int> counter(n + 1);
    int r = 0;
    for (int i = 1; i <= n; i++) {
        r = (r + number[i-1] - '0') % 3;
        counter[i] = counter[i-1];
        if (remIndex[r] != -1)
            counter[i] = max(counter[i], counter[remIndex[r]] + 1);
        remIndex[r] = i+1;
    }
    return counter[n];
}

int main() {
    string number = "216873491";
    cout << "संख्या " << number << " को काटकर बने 3 विभाज्य संख्याओं की संख्या है: " << countMaximum3DivisibleNumbers(number);
    return 0;
}

आउटपुट

संख्या 216873491 को काटकर बने 3 विभाज्य संख्याओं की संख्या है: 5