এই সমস্যায়, আমাদের একটি বড় পূর্ণসংখ্যা মান দেওয়া হয়েছে (10 5 পর্যন্ত) অঙ্ক)। আমাদের কাজ হল প্রয়োজনীয় মোট সংখ্যা প্রিন্ট করা যাতে সর্বাধিক অংশগুলি 3 দ্বারা বিভাজ্য হয়।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক
ইনপুট − 9216
আউটপুট৷ − 3
ব্যাখ্যা − সংখ্যাটিকে 9|21|6 হিসাবে ভাগ করা হয়েছে।
এই সমস্যাটি সমাধান করার জন্য, আমাদের সংখ্যার ন্যূনতম উল্লেখযোগ্য বিট অর্থাৎ সংখ্যাটির শেষ সংখ্যার জন্য শুরু করতে হবে। এখানে, আমরা তিনটি দ্বারা বিভাজ্য ক্ষুদ্রতম সংখ্যাটি খুঁজে পাব। এবং তারপর এটির উপর ভিত্তি করে গণনা আপডেট করুন।
উদাহরণ − যদি arr[i] একটি 3 বিভাজ্য সংখ্যা তৈরি করে, তাহলে আমরা গণনা বাড়াব এবং সংখ্যাটির পরবর্তী সংখ্যায় চলে যাব। যদি arr[i] 3 দ্বারা বিভাজ্য না হয়, তাহলে আমরা পরবর্তী অঙ্কের সাথে এটিকে একত্রিত করব এবং 3-এর বিভাজ্যতা পরীক্ষা করব।
3 এর বিভাজ্যতা − একটি সংখ্যা 3 দ্বারা বিভাজ্য যদি সংখ্যাটির সংখ্যা তিনটি দ্বারা বিভাজ্য হয়৷
উদাহরণ
আমাদের সমাধানের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
int countMaximum3DivisibleNumbers(string number){
int n = number.length();
vector<int> remIndex(3, -1);
remIndex[0] = 0;
vector<int> counter(n + 1);
int r = 0;
for (int i = 1; i <= n; i++) {
r = (r + number[i-1] - '0') % 3;
counter[i] = counter[i-1];
if (remIndex[r] != -1)
counter[i] = max(counter[i], counter[remIndex[r]] + 1);
remIndex[r] = i+1;
}
return counter[n];
}
int main() {
string number = "216873491";
cout<<"The number of 3 divisible number created by cutting "<<number<<" are : " <<countMaximum3DivisibleNumbers(number);
return 0;
} আউটপুট
The number of 3 divisible number created by cutting 216873491 are : 5
