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 भागों में विभाजित कर देते हैं।