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

C++ में पूर्णांकों की स्ट्रिंग में 6 से विभाज्य सबस्ट्रिंग्स की संख्या


हम एक ऐसी समस्या को देखेंगे जिसमें हमें एक पूर्णांक स्ट्रिंग दी गई है और यह निर्धारित करना है कि पूर्णांक प्रारूप में कितने सबस्ट्रिंग्स 6 से विभाज्य हैं। यह ध्यान दिया जाना चाहिए कि इनपुट संख्याओं (पूर्णांकों) से बनी स्ट्रिंग के रूप में है। फिर भी, विभाज्यता जांच केवल पूर्णांक के रूप में की जाएगी (स्ट्रिंग इनपुट के ASCII मान का उपयोग नहीं करके)।

इनपुट

str = "648"

आउटपुट

व्याख्या

सबस्ट्रिंग "6", "48", और "648" 6 से विभाज्य हैं।

इनपुट

str = "38342"

आउटपुट

4

व्याख्या

सबस्ट्रिंग्स "3834", "342", "834", और "42" 6 से विभाज्य हैं।

ब्रूट-फोर्स दृष्टिकोण

उपयोगकर्ता हर संभव सबस्ट्रिंग को जांच सकते हैं कि क्या यह 6 से विभाज्य है। यदि सबस्ट्रिंग विभाज्य है, तो हम अतिरिक्त रूप से इसे गिनते हैं। इस विधि से समस्या हल करने में अधिक समय लगेगा और कार्य पूरा करने में O(n²) समय लगेगा।

उदाहरण

#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) - i-वें इंडेक्स से उन स्ट्रिंग्स की संख्या जिनके अंकों का योग मॉड्यूलो 3 है s जो Σin-1 f(i,0) देता है।

मान लें a स्ट्रिंग का i-वां अंक है; अब, f(i,s) से, हमें उन सभी सबस्ट्रिंग्स को ढूंढना होगा जो सम हैं और i + 1 से शुरू होती हैं। यदि (a+s) 3 से विभाज्य है, तो एक अतिरिक्त सबस्ट्रिंग उत्पन्न की जा सकती है। तो, हमारा पुनरावृत्ति संबंध बना,

f(i,s) = f(i + 1, (s + a)%3) + ( a%2 == 0 AND (a+s)%3 == 0)।

उदाहरण 2

#include <bits/stdc++.h> using namespace std; int find(int i, int s, char str[], int dp[][3]){    // जब स्ट्रिंग के अंत तक पहुंच गए।    if (i == strlen(str))       return 0;    // यदि पहले से गणना की गई है तो परिणाम वापस करें।    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 सरणी।    int dp[n+1][3];    memset(dp, -1, sizeof dp);    int count = 0;    for (int i = 0; i < n; i++){       // यदि कोई स्थिति 0 रखती है तो काउंट बढ़ाएं।       if (str[i] == '0')          count++;       // पुनरावर्ती फ़ंक्शन में पिछला योग मॉड्यूलो 3 = 0 पास करना।       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, जावा, पायथन और अन्य जैसी विभिन्न भाषाओं में लिखा जा सकता है। हमें आशा है कि आपको यह पाठ उपयोगी लगा।

  1. - C++ कोड: संख्यात्मक स्ट्रिंग के सम सबस्ट्रिंग की गणना करें

    मान लीजिए हमारे पास n अंकों का एक स्ट्रिंग S है। S का एक सबस्ट्रिंग सम कहा जाता है यदि इस स्ट्रिंग द्वारा दर्शाई गई संख्या भी सम है। हमें S के सम सबस्ट्रिंग की संख्या ढूंढनी है।उदाहरण के लिए, यदि इनपुट S = 1234 है, तो आउटपुट 6 होगा, क्योंकि सबस्ट्रिंग हैं 2, 4, 12, 34, 234, 1234।इसे हल करने के लिए,

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

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

  1. C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना

    इस लेख में, आप एक दी गई स्ट्रिंग में बनने वाले सबस्ट्रिंग्स (गैर-खाली) की संख्या निकालने के दृष्टिकोण के बारे में जानेंगे।इनपुट: string = moon आउटपुट: 10 व्याख्या: सबस्ट्रिंग्स हैं m, o, o, n, mo, oo, on, moo, oon और moon। इनपुट: string = yellow आउटपुट: 21समाधान खोजने का दृष्टिकोणमान लें स्ट्रिंग की