আমরা একটি সমস্যা দেখব যেখানে আমাদের একটি পূর্ণসংখ্যা স্ট্রিং দেওয়া হয়েছে এবং পূর্ণসংখ্যা বিন্যাসে কতগুলি সাবস্ট্রিং 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) দেয়।
একটি স্ট্রিং এর 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 দ্বারা বিভাজ্য সাবস্ট্রিংগুলির সংখ্যা আবিষ্কার করতে হয়। একই প্রোগ্রাম বিভিন্ন ভাষায় লেখা হতে পারে যেমন সি, জাভা, পাইথন এবং অন্যান্য। আমরা আশা করি আপনি এই পাঠটি উপকারী বলে মনে করেছেন।
