C++-এ সাইজ K-এর সাবসেটের গুণফলে ট্রেইলিং জিরোর সর্বোচ্চ সংখ্যা

দেওয়া কাজ হল একটি N আকারের অ্যারের সাইজ K-এর সাবসেটের গুণফলে ট্রেইলিং জিরোর সর্বোচ্চ সংখ্যা খুঁজে বের করা।

উদাহরণ দিয়ে বোঝা যাক

ইনপুট - Arr[] = {5, 20, 2}, K=2

আউটপুট - ২

ব্যাখ্যা - সাইজ ২-র মোট ৩টি সাবসেট তৈরি করা যায়। [5, 20] এর গুণফল ১০০। [20, 2] এর গুণফল ৪০। [5, 2] এর গুণফল ১০। ১০০-এ সর্বোচ্চ ২টি ট্রেইলিং জিরো আছে। তাই উত্তর ২।

ইনপুট - Arr[] = {60, 40, 25}, K=2

আউটপুট - ৩

প্রোগ্রামে ব্যবহৃত পদ্ধতি

ফাংশন শুরু করার আগে উপরে #define M5 100 ডিফাইন করুন।
MaxZeros() ফাংশনে একটি ২D অ্যারে Sub[K + 1][M5 + 5] তৈরি করুন এবং এর প্রতিটি মান -1 দিয়ে আরম্ভ করুন এবং Sub[0][0] = 0 সেট করুন।
P=0 থেকে P<N পর্যন্ত লুপ চালান এবং লুপের ভেতরে P2 = 0 এবং P5 = 0 ইন্টিজার আরম্ভ করুন যা যথাক্রমে দেওয়া সংখ্যায় ২ এবং ৫-এর সংখ্যা সংরক্ষণ করবে।
while(Arr[P]%2 == 0) কন্ডিশন সহ একটি হুইল লুপ শুরু করুন এবং লুপের ভেতরে P2++ এবং Arr[P]/=2 করুন ২-এর সংখ্যা বের করার জন্য। P5-এর জন্য একই ধাপ दुहरান।
উপরোক্ত ফর লুপের ভেতরে আরও দুটি নেস্টেড ফর লুপ আরম্ভ করুন - for (int i = K - 1; i >= 0; i--) এবং for (int j = 0; j < M5; j++)।
এই লুপগুলোতে চেক করুন if(Sub[i][j] != -1) এবং যদি সত্য হয় তবে Sub[i + 1][j + P5] = max(Sub[i + 1][j + P5], Sub[i][j] + P2); সেট করুন।

C++ প্রোগ্রাম উদাহরণ

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

int MaxZeros(int* Arr, int N, int K){
    // প্রতিটি মান -1 দিয়ে আরম্ভ করা
    int Sub[K+1][M5+5];
    memset(Sub, -1, sizeof(Sub));
    Sub[0][0] = 0;
    
    for (int P = 0; P < N; P++){
        int P2 = 0, P5 = 0;
        // Arr[P]-এ ২-এর সর্বোচ্চ ঘাত
        while (Arr[P] % 2 == 0){
            P2++;
            Arr[P] /= 2;
        }
        // Arr[P]-এ ৫-এর সর্বোচ্চ ঘাত
        while (Arr[P] % 5 == 0) {
            P5++;
            Arr[P] /= 5;
        }
        /* আমরা ২ সংগ্রহ করতে পারি প্রথম i সংখ্যা চেক করে এবং তাদের j নিয়ে ৫-এর মোট ঘাত বের করে*/
        for (int i = K - 1; i >= 0; i--)
            for (int j = 0; j < M5; j++)
            // যদি subset[i][j] ক্যালকুলেট না হয়
            if (Sub[i][j] != -1)
                Sub[i + 1][j + P5] = max(Sub[i + 1][j + P5], Sub[i][j] + P2);
    }
    /* ৫ বা ২-এর মিনিমাম নিয়ে রেজাল্ট ম্যাক্সিমাইজ করা*/
    int ans = 0;
    for (int i = 0; i < M5; i++)
        ans = max(ans, min(i, Sub[K][i]));
    return ans;
}

// মেইন ফাংশন
int main(){
    int Arr[] = { 60, 40, 25 };
    int K = 2;
    int N = sizeof(Arr) / sizeof(Arr[0]);
    cout << MaxZeros(Arr, N, K);
    return 0;
}