একটি পূর্ণসংখ্যা স্ট্রিং দেওয়া আছে। ৬ দিয়ে বিভাজ্য সাবস্ট্রিংয়ের সংখ্যা বের করতে হবে।
ইনপুট/আউটপুট উদাহরণ
ইনপুট: "648" → আউটপুট: 3 (সাবস্ট্রিং: "6", "48", "648")
ইনপুট: "38342" → আউটপুট: 4 (সাবস্ট্রিং: "3834", "342", "834", "42")
ব্রুট-ফোর্স পদ্ধতি
সব সম্ভাব্য সাবস্ট্রিং চেক করুন। 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), count = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
if (str_to_int(str, i, j) % 6 == 0) count++;
cout << count << endl;
return 0;
}
আউটপুট
6
দক্ষ পদ্ধতি (ডাইনামিক প্রোগ্রামিং)
৬ দিয়ে বিভাজ্যতার জন্য: শেষ অঙ্ক জোড় হতে হবে এবং অঙ্কগুলোর যোগফল ৩ দিয়ে বিভাজ্য হতে হবে। DP[i][s] = i-তম ইনডেক্স থেকে শুরু করে যোগফল মডুলো ৩ = s এমন সাবস্ট্রিংয়ের সংখ্যা। রিকারেন্স: f(i,s) = f(i+1, (s+a)%3) + (a%2==0 && (a+s)%3==0)।
উদাহরণ ২ (DP)
#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);
int dp[n+1][3];
memset(dp, -1, sizeof dp);
int count = 0;
for (int i = 0; i < n; i++) {
if (str[i] == '0') count++;
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) সময়ে ৬ দিয়ে বিভাজ্য সাবস্ট্রিং গণনা করা হয়েছে।
