প্রদত্ত টাস্ক হল N আকারের একটি প্রদত্ত বিন্যাসের K আকারের উপসেটের গুণফলের মধ্যে সর্বাধিক সংখ্যক অনুগামী শূন্য খুঁজে বের করা।
আসুন এখন বুঝতে পারি একটি উদাহরণ ব্যবহার করে আমাদের কী করতে হবে −
ইনপুট − Arr[] ={5, 20, 2} , K=2
আউটপুট৷ − 2
ব্যাখ্যা − মোট 3টি উপসেট তৈরি করা যেতে পারে যার আকার =2।
[5, 20] এর গুণফল হল 100।
[20, 2] এর গুণফল হল 40।
[5, 2] এর গুণফল হল 10।
100-এর সর্বাধিক সংখ্যক শূন্য শূন্য =2। তাই 2 হল উত্তর।
ইনপুট − Arr[] ={60, 40, 25} , K=2
আউটপুট − 3
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
ফাংশন শুরু করার আগে, উপরে M5 100 ডিফাইন করুন।
-
MaxZeros() ফাংশনে একটি 2D অ্যারে সাব[K + 1][M5 + 5] তৈরি করুন এবং এর প্রতিটি মান -1 দিয়ে শুরু করুন এবং Sub[0][0] =0;
সেট করুন -
P=0 থেকে P
-
কন্ডিশন সহ একটি while লুপ শুরু করুন (Arr[P]%2 ==0) এবং লুপের ভিতরে 2s সংখ্যা পেতে P2++ এবং Arr[P]/2 করুন। P5 এর জন্য একই ধাপ পুনরাবৃত্তি করুন।
-
তারপর উপরের শুরুর ভিতরে For loop ইনিশিয়ালাইজ করুন নিচের মতো লুপের জন্য আরও দুটি নেস্টেড -
জন্য (int i =K - 1; i>=0; i--)
জন্য (int j =0; j
-
এই লুপের ভিতরে চেক করুন যদি(Sub[i][j] !=-1) এবং যদি এটি সত্য হয় তাহলে Sub[i + 1][j + P5] =max(Sub[i + 1];[j + P5) রাখুন ], Sub[i][j] + P2);
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define M5 100
int MaxZeros(int* Arr, int N, int K){
//Initializing each value with -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;
// Maximal power of 2 in Arr[P]
while (Arr[P] % 2 == 0){
P2++;
Arr[P] /= 2;
}
// Maximal power of 2 in Arr[P]
while (Arr[P] % 5 == 0) {
P5++;
Arr[P] /= 5;
}
/* We can collect 2s by checking first i numbers and taking their j with total power of 5*/
for (int i = K - 1; i >= 0; i--)
for (int j = 0; j < M5; j++)
// If subset[i][j] is not calculated.
if (Sub[i][j] != -1)
Sub[i + 1][j + P5] = max(Sub[i + 1][j + P5], Sub[i][j] + P2);
}
/* Taking minimum of 5 or 2 and maximizing the result*/
int ans = 0;
for (int i = 0; i < M5; i++)
ans = max(ans, min(i, Sub[K][i]));
return ans;
}
//Main function
int main(){
int Arr[] = { 60, 40, 25 };
int K = 2;
int N = sizeof(Arr) / sizeof(Arr[0]);
cout << MaxZeros(Arr, N, K);
return 0;
} আউটপুট
আমরা উপরের কোডটি চালালে আমরা নিম্নলিখিত আউটপুট পাব −
3
