हम एक समस्या को देखेंगे जिसमें हमें एक पूर्णांक स्ट्रिंग दी गई है और यह निर्धारित करना होगा कि पूर्णांक प्रारूप में कितने सबस्ट्रिंग 6 से विभाज्य हैं। यह ध्यान दिया जाना चाहिए कि इनपुट संख्याओं (पूर्णांक) से बने स्ट्रिंग के रूप में है। फिर भी, विभाज्यता जांच इसे केवल एक पूर्णांक के रूप में मानते हुए की जाएगी (स्ट्रिंग इनपुट के ASCII मान का उपयोग नहीं)।
इनपुट
str = “648”
आउटपुट
स्पष्टीकरण
सबस्ट्रिंग "6", "48", और "648" 6 से विभाज्य हैं।
इनपुट
str = “38342”
आउटपुट
4
स्पष्टीकरण
सबस्ट्रिंग "3834", "342", "834", और "42" 6 से विभाज्य हैं।
ब्रूट-फोर्स अप्रोच
उपयोगकर्ता यह देखने के लिए हर संभव विकल्प की जांच कर सकते हैं कि क्या यह छह से विभाज्य है। यदि सबस्ट्रिंग विभाज्य है, तो हम इसे अतिरिक्त रूप से गिनते हैं। इस विधि से समस्या को हल करने में अधिक समय लगेगा और कार्य को पूरा करने में O(n2) समय लगेगा।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int
str_to_int (string str, int i, int j) {
int temp = 0;
for (; i <= j; i++) {
temp = temp * 10 + (str[i] - '0');
}
return temp;
}
int main () {
char str[] = "24661";
int n = strlen (str);
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int temp = str_to_int (str, i, j);
if (temp % 6 == 0) count++;
}
}
cout << count << endl;
return 0;
} आउटपुट
6
कुशल दृष्टिकोण
किसी संख्या का अंतिम अंक 2 से विभाज्य होना चाहिए ताकि वह 6 से विभाज्य हो। अंकों की कुल संख्या 3 होनी चाहिए। पहले से गणना किए गए उत्तरों को ट्रैक करके, हम समाधान खोजने के लिए गतिशील प्रोग्रामिंग का उपयोग कर सकते हैं।
चलो f(i,s) - ith इंडेक्स से स्ट्रिंग्स की संख्या जिसका अंक योग मॉड्यूल 3 s है जो Σin-1 f(i,0) देता है।
मान लीजिए a एक स्ट्रिंग का ith अंक है; अब, f(i,s) से, हमें सभी सबस्ट्रिंग खोजने की जरूरत है जो सम हैं और i + 1 से शुरू होते हैं। यदि (a+s) 3 से विभाज्य है, तो एक अतिरिक्त सबस्ट्रिंग का उत्पादन किया जा सकता है। तो, हमारा पुनरावृत्ति संबंध बनता है ,
f(i,s) =f(i + 1, (s + a)%3) + ( a%2 ==0 और (a+s)%3 ==0)।
उदाहरण 2
#include <bits/stdc++.h>
using namespace std;
int find(int i, int s, char str[], int dp[][3]){
// when reached end of string.
if (i == strlen(str))
return 0;
// if already computed then return result.
if (dp[i][s] != -1)
return dp[i][s];
int a = str[i] - '0';
int ans = ((a+s)%3 == 0 && a%2 == 0) + find(i+1, (s+a)%3, str, dp);
return dp[i][s] = ans;
}
int main(){
char str[] = "24661";
int n = strlen(str);
// dp array to store all states.
int dp[n+1][3];
memset(dp, -1, sizeof dp);
int count = 0;
for (int i = 0; i < n; i++){
// if any position contains 0 increment count.
if (str[i] == '0')
count++;
// Passing previous sum modulo 3 = 0 to recursive function.
else
count += find(i, 0, str, dp);
}
cout << "Number of substrings divisible by 6: " << count << endl;
return 0;
} आउटपुट
Number of substrings divisible by 6: 6
समय जटिलता:O(N)
निष्कर्ष
इस ट्यूटोरियल में, हमने सीखा कि पूर्णांकों की एक स्ट्रिंग में 6 से विभाज्य सबस्ट्रिंग की संख्या को खोजने के लिए डायनेमिक प्रोग्रामिंग का उपयोग कैसे करें। एक ही प्रोग्राम को विभिन्न भाषाओं जैसे C, Java, Python और अन्य में लिखा जा सकता है। हम आशा करते हैं कि आपको यह पाठ लाभदायक लगा होगा।