C++-এ একটি সংখ্যা কাটা যাতে সর্বাধিক অংশ ৩ দিয়ে বিভাজ্য হয়

এই সমস্যাতে, একটি বড় পূর্ণসংখ্যা (১০⁵ ডিজিট পর্যন্ত) দেওয়া আছে। আমাদের কাজ হলো প্রিন্ট করা মোট কতটি কাট লাগবে যাতে সর্বাধিক অংশ ৩ দিয়ে বিভাজ্য হয়।

উদাহরণ:

ইনপুট - 9216

আউটপুট - 3

ব্যাখ্যা - সংখ্যাটি ভাগ করা হয়েছে 9|21|6 হিসেবে।

সমাধানের জন্য, আমাদের সংখ্যার লিস্ট সিগনিফিক্যান্ট বিট অর্থাৎ শেষ ডিজিট থেকে শুরু করতে হবে। এখানে, আমরা সবচেয়ে ছোট ৩ দিয়ে বিভাজ্য সংখ্যা খুঁজে বের করব। এবং তার উপর ভিত্তি করে কাউন্ট আপডেট করব।

উদাহরণ - যদি arr[i] ৩ দিয়ে বিভাজ্য সংখ্যা বানাবে, তবে কাউন্ট বাড়াব এবং সংখ্যার পরবর্তী ডিজিটে যাব। যদি arr[i] ৩ দিয়ে বিভাজ্য না হয়, তবে এটিকে পরবর্তী ডিজিটের সাথে কম্বাইন করে ৩ দিয়ে বিভাজ্যতা চেক করব।

৩ দিয়ে বিভাজ্যতা - একটি সংখ্যা ৩ দিয়ে বিভাজ্য হয় যদি এর ডিজিটগুলোর যোগফল ৩ দিয়ে বিভাজ্য হয়।

উদাহরণ

সমাধানের প্রোগ্রাম:

#include <bits/stdc++.h> 
using namespace std; 

int countMaximum3DivisibleNumbers(string number) {
    int n = number.length();
    vector remIndex(3, -1);
    remIndex[0] = 0;
    vector 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