मान लीजिए कि हमारे पास ProductOfNumbers नामक वर्ग लागू है जो दो विधियों का समर्थन करता है -
-
add(int num):यह संख्या संख्या को संख्याओं की वर्तमान सूची के पीछे जोड़ता है।
-
getProduct(int k):यह वर्तमान सूची में अंतिम k संख्याओं का गुणनफल देता है।
हम मान सकते हैं कि हमेशा वर्तमान सूची में कम से कम k संख्याएँ होती हैं। तो उदाहरण के लिए, यदि इनपुट की तरह है - जोड़ें(3), जोड़ें(0), जोड़ें(2), जोड़ें(5), जोड़ें(4), उत्पाद(2), getProduct(3), getProduct(4), add(8), getProduct(2), तो आउटपुट होगा (प्रत्येक फंक्शन कॉल के बाद) -
[3], [3, 0], [3, 0, 2], [3, 0, 2, 5], [3, 0, 2, 5, 4], then (5 * 4) = 20, then (2 * 5 * 4) = 40, then (0 * 2 * 5 * 4) = 0, then [3, 0, 2, 5, 4, 8], then (4 * 8) = 32.
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
आरंभीकरण अनुभाग में, यह एक सरणी बनाएगा, और उसमें 1 डाल देगा
-
जोड़ें () विधि संख्या लेगी
-
यदि संख्या 0 है, तो सरणी को साफ़ करें, और 1 डालें, अन्यथा last_element * num को सरणी में डालें
-
getProduct() विधि k को इनपुट के रूप में लेगी
-
n :=सरणी का आकार
-
अगर k> n – 1, तो 0 लौटाएं, अन्यथा dp[n - 1] / dp[n – k – 1]
उदाहरण (C++)
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
class ProductOfNumbers {
public:
vector <int> dq;
ProductOfNumbers() {
dq.push_back(1);
}
void add(int num) {
if(num == 0){
dq.clear();
dq.push_back(1);
}
else{
dq.push_back(dq.back() * num);
}
}
int getProduct(int k) {
int n = (int)dq.size();
return k > n - 1? 0 : dq[n - 1] / dq[n - k - 1];
}
};
main(){
ProductOfNumbers ob;
(ob.add(3));
(ob.add(0));
(ob.add(2));
(ob.add(5));
(ob.add(4));
cout << (ob.getProduct(2)) << endl;
cout << (ob.getProduct(3)) << endl;
cout << (ob.getProduct(4)) << endl;
(ob.add(8));
cout << (ob.getProduct(2)) << endl;
} इनपुट
add(3) add(0) add(2) add(5) add(4) getProduct(2) getProduct(3) getProduct(4) add(8) getProduct(2)
आउटपुट
20 40 0 32