यह देखते हुए कि आकार N के दिए गए सरणी के आकार K के उपसमुच्चय के गुणनफल में अनुगामी शून्यों की अधिकतम संख्या ज्ञात करना है।
आइए अब समझते हैं कि हमें एक उदाहरण का उपयोग करके क्या करना है -
इनपुट - Arr[] ={5, 20, 2} , K=2
आउटपुट -2
स्पष्टीकरण - आकार =2 वाले कुल 3 उपसमुच्चय बनाए जा सकते हैं।
[5, 20] का गुणनफल 100 है।
[20, 2] का गुणनफल 40 है।
[5, 2] का गुणनफल 10 है।
100 में अनुगामी शून्यों की अधिकतम संख्या =2 है। इसलिए 2 उत्तर है।
इनपुट - Arr[] ={60, 40, 25} , K=2
आउटपुट -3
निम्नलिखित कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है
-
फंक्शन शुरू करने से पहले, शीर्ष पर #define M5 100.
-
फ़ंक्शन में MaxZeros() एक 2D सरणी Sub[K + 1][M5 + 5] बनाएं और इसके प्रत्येक मान को -1 से प्रारंभ करें और Sub[0][0] =0;
सेट करें। -
P=0 से P
-
कंडीशन के साथ थोड़ी देर के लूप को शुरू करें जबकि (Arr[P]%2 ==0) और लूप के अंदर 2s की संख्या प्राप्त करने के लिए P2++ और Arr[P]/2 करें। P5 के लिए भी यही चरण दोहराएं।
-
फिर ऊपर के अंदर शुरू हुआ लूप के लिए लूप के लिए दो और नेस्टेड इनिशियलाइज़ करें -
के लिए (int i =K - 1; i>=0; i--)
के लिए (int j =0; j
-
इन लूपों के अंदर जांचें कि क्या (उप [i] [जे]! =-1) और यदि यह सत्य है तो उप [i + 1] [j + P5] =अधिकतम (उप [i + 1]; [j + P5 डालें) ], उप[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