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]।
যেকোনো সূচকে i 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 ভাগে ভাগ করলে এটি একটি খুব সোজা সমস্যা৷
