0-9 की एक स्ट्रिंग दी गई है। इस समस्या के लिए, हमें उन स्ट्रिंग्स की संख्या की गणना करने की आवश्यकता है जो 8 से विभाज्य हैं और 3 से नहीं। यह एक 2 कदम की समस्या है, और हमें इसे हल करने के लिए एक बार में कोड को एक कदम करने की आवश्यकता है, उदाहरण के लिए
इनपुट
str = "80"
आउटपुट
2
इनपुट
str = "7675636788"
आउटपुट
15
समाधान खोजने के लिए दृष्टिकोण
केवल अंतिम 3 अंकों वाली संख्याएं 8 से विभाज्य होती हैं, और उनके 3 से विभाज्य अंकों का योग 8 से विभाज्य होता है।
अब स्ट्रिंग के प्रीफ़िक्स योग को स्टोर करें ताकि प्रीफ़िक्स मॉड्यूल 3 के अंकों का योग या तो 0,1 या 2 हो। फिर स्ट्रिंग को i के सभी पदों के लिए पुनरावृत्त किया जाता है। फिर i पर सबस्ट्रिंग की संख्या गिनें, जो 8 से विभाज्य हैं—अब, i पर सबस्ट्रिंग की संख्या घटाकर, जो इस मान से 3 से विभाज्य हैं।
|एस| X 3 आकार 2D सरणी परिभाषित है, |S| एक स्ट्रिंग का आकार है, dp[i][j] कहें।
किसी भी सूचकांक में मैं 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++;
}
// Taking 3 digit number.
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++ कोड के साथ-साथ 3 से नहीं 8 से विभाज्य सबस्ट्रिंग की संख्या कैसे ज्ञात की जाती है। यह कोड जावा, पायथन और अन्य भाषाओं में भी लिखा जा सकता है। इस समस्या को हल करने के लिए, हमने 8 से विभाज्य लेकिन 3 से विभाज्य नहीं होने वाले सबस्ट्रिंग की संख्या को खोजने के लिए एक स्ट्रिंग को उलट दिया है। जब हम इसे 2 भागों में विभाजित करते हैं तो यह एक बहुत ही सीधी समस्या है।