C++ में आकार k के सबसेट के गुणनफल में अधिकतम अनुगामी शून्य

दिया गया कार्य दिए गए आकार 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<N तक लूप चलाएं और लूप के अंदर P2 = 0 और P5 = 0 दोनों को int टाइप का आरंभ करें जो दी गई संख्या में 2 और 5 की संख्या स्टोर करने के लिए उपयोग किए जाएंगे।
शर्त while(Arr[P]%2 == 0) के साथ एक व्हाइल लूप शुरू करें और लूप के अंदर P2++ और Arr[P]/=2 करें 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] में 2 की अधिकतम घात
        while (Arr[P] % 2 == 0) {
            P2++;
            Arr[P] /= 2;
        }
        
        // Arr[P] में 5 की अधिकतम घात
        while (Arr[P] % 5 == 0) {
            P5++;
            Arr[P] /= 5;
        }
        
        /* हम पहले i संख्याओं को चेक करके और उनकी कुल 5 की घात के साथ j लेकर 2 एकत्र कर सकते हैं */
        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);
    }
    
    /* 5 या 2 का न्यूनतम लेकर परिणाम को अधिकतम करना */
    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;
}