Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में 8 से विभाज्य और 3 से नहीं विभाज्य सबस्ट्रिंग्स की संख्या


0-9 की एक स्ट्रिंग दी गई है। इस समस्या के लिए, हमें उन स्ट्रिंग्स की संख्या की गणना करने की आवश्यकता है जो 8 से विभाज्य हैं और 3 से नहीं। यह एक 2-चरण की समस्या है, और हमें इसे हल करने के लिए एक बार में एक चरण का कोड करना होगा, उदाहरण के लिए

इनपुट

str = "80"

आउटपुट

2

इनपुट

str = "7675636788"

आउटपुट

15

समाधान खोजने का दृष्टिकोण

केवल वही संख्याएं जिनके अंतिम 3 अंक 8 से विभाज्य होते हैं, और जिनके अंकों का योग 3 से विभाज्य होता है, 8 से विभाज्य होती हैं।

अब स्ट्रिंग का प्रीफिक्स योग संग्रहीत करें ताकि अंकों का योग प्रीफिक्स मॉड्यूलो 3 या तो 0, 1, या 2 हो। फिर स्ट्रिंग को i की सभी स्थितियों के लिए दोहराएं। फिर i पर उन सबस्ट्रिंग्स की संख्या गिनें जो 8 से विभाज्य हैं - अब इस मान से i पर उन सबस्ट्रिंग्स की संख्या घटाएं जो 3 से विभाज्य हैं।

|S| X 3 आकार की 2D सरणी परिभाषित की गई है, |S| स्ट्रिंग का आकार है, मान लें dp[i][j]।

किसी भी इंडेक्स i पर dp[i][j]। इंडेक्स i से 0 तक शुरू होने पर, सबस्ट्रिंग्स की संख्या जिनका आउटपुट j है। तो 0<=j<=0, चूंकि मॉड्यूलो 3।

हमें स्ट्रिंग पर पुनरावृति करने की आवश्यकता है ताकि यह जांचा जा सके कि एक-अंकीय, दो-अंकीय और तीन-अंकीय संख्याएं 8 से विभाज्य हैं या नहीं।

  • इंडेक्स पर वर्ण 8 है या नहीं, यह निर्धारित करने के लिए इंडेक्स पर संख्या जांचें।

  • यदि दो अंक हैं तो 3 के बजाय 8 से विभाजित करें।

आइए मान लें कि संख्या 8 से विभाज्य है। यदि यह 8 से विभाज्य है तो इसमें दो (1-3) सबस्ट्रिंग्स होनी चाहिए। हालांकि, इसमें वे सबस्ट्रिंग्स भी होंगी जो 8 से विभाज्य हैं। उन्हें हटाने के लिए।

उदाहरण

#include <bits/stdc++.h> using namespace std; #define MAX 1000 int count (char s[], int len) {    int cur = 0,    dig = 0;    int sum[MAX], dp[MAX][3];    memset (sum, 0, sizeof (sum));    memset (dp, 0, sizeof (dp));    dp[0][0] = 1;    for (int i = 1; i <= len; i++) {       dig = int (s[i - 1]) - 48;       cur += dig;       cur %= 3;       sum[i] = cur;       dp[i][0] = dp[i - 1][0];       dp[i][1] = dp[i - 1][1];       dp[i][2] = dp[i - 1][2];       dp[i][sum[i]]++;    }    int ans = 0, dprev = 0, value = 0, dprev2 = 0;    for (int i = 1; i <= len; i++) {       dig = int (s[i - 1]) - 48;       if (dig == 8) ans++;       if (i - 2 >= 0) {          dprev = int (s[i - 2]) - 48;          value = dprev * 10 + dig;          if ((value % 8 == 0) && (value % 3 != 0)) ans++;       }       // 3 अंकों की संख्या लेना।       if (i - 3 >= 0){          dprev2 = int (s[i - 3]) - 48;          dprev = int (s[i - 2]) - 48;          value = dprev2 * 100 + dprev * 10 + dig;          if (value % 8 != 0) continue;             ans += (i - 2);          ans -= (dp[i - 3][sum[i]]);       }    }    return ans; } int main () {    char str[] = "7675636788";    int len = strlen (str);    cout << count (str, len) << endl;    return 0; }

आउटपुट

4

निष्कर्ष

इस समस्या में, हमने C++ कोड के साथ 8 से विभाज्य और 3 से नहीं विभाज्य सबस्ट्रिंग्स की संख्या ढूंढना सीखा। यह कोड जावा, पायथन और अन्य भाषाओं में भी लिखा जा सकता है। इस समस्या को हल करने के लिए, हमने 8 से विभाज्य लेकिन 3 से विभाज्य नहीं सबस्ट्रिंग्स की संख्या ढूंढने के लिए एक स्ट्रिंग को उल्टा किया है। यह एक बहुत सीधी समस्या है एक बार जब हम इसे 2 भागों में विभाजित कर देते हैं।

  1. - C++ में जांचें कि क्या बड़ी संख्या 20 से विभाज्य है

    यहां हम देखेंगे कि कैसे जांचें कि कोई संख्या 20 से विभाज्य है या नहीं। इस मामले में संख्या बहुत बड़ी है। इसलिए हम संख्या को स्ट्रिंग के रूप में रखते हैं। एक संख्या 20 से विभाज्य होगी, जब वह 10 से विभाज्य हो, और 10 से विभाजित करने के बाद, शेष संख्या 2 से विभाज्य हो। तो मामला सरल है। यदि अंतिम अंक 0

  1. - C++ में जांचें कि क्या बड़ी संख्या 2, 3 और 5 से विभाज्य है या नहीं

    यहां हम देखेंगे कि कैसे जांचें कि कोई संख्या 2, 3 और 5 से विभाज्य है या नहीं। इस मामले में संख्या बहुत बड़ी है। इसलिए हम संख्या को स्ट्रिंग के रूप में रखते हैं। एक संख्या 2, 3 और 5 से विभाज्य होगी यदि वह संख्या 2, 3 और 5 के LCM से विभाज्य है। तो 2, 3, 5 का LCM 30 है। हमें जांचना होगा कि संख्या 30 स

  1. - C++ में जांचें कि क्या बड़ी संख्या 11 से विभाज्य है या नहीं

    यहां हम देखेंगे कि कैसे जांचें कि कोई संख्या 11 से विभाज्य है या नहीं। इस मामले में संख्या बहुत बड़ी है। इसलिए हम संख्या को स्ट्रिंग के रूप में रखते हैं। यह जांचने के लिए कि कोई संख्या 11 से विभाज्य है या नहीं, यदि विषम स्थिति के मानों का योग और सम स्थिति के मानों का योग समान है, तो संख्या 11 से वि