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

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

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

इनपुट - 9216

आउटपुट -3

स्पष्टीकरण - संख्या को 9|21|6 से विभाजित किया जाता है।

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

उदाहरण - अगर arr[i] एक 3 विभाज्य संख्या बनाता है, तो हम गिनती बढ़ाएंगे और संख्या के अगले अंक की ओर बढ़ेंगे। अगर arr[i] 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<<"The number of 3 divisible number created by cutting "<<number<<" are : " <<countMaximum3DivisibleNumbers(number);
   return 0;
}

आउटपुट

The number of 3 divisible number created by cutting 216873491 are : 5