ধরুন আমাদের কাছে ProductOfNumbers নামক ক্লাসটি বাস্তবায়ন আছে যা দুটি পদ্ধতি সমর্থন করে -
-
add(int num):এটি সংখ্যার বর্তমান তালিকার পিছনের সংখ্যা যোগ করে।
-
getProduct(int k):এটি বর্তমান তালিকার শেষ k সংখ্যার গুণফল প্রদান করে।
আমরা ধরে নিতে পারি যে বর্তমান তালিকায় সর্বদা কমপক্ষে k সংখ্যা থাকে। সুতরাং উদাহরণস্বরূপ, যদি ইনপুটটি হয় − add(3), add(0), add(2), add(5), add(4), getProduct(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 রাখবে
-
add() পদ্ধতিতে num লাগবে
-
যদি সংখ্যা 0 হয়, তাহলে অ্যারেটি সাফ করুন এবং 1 সন্নিবেশ করুন, অন্যথায় অ্যারেতে last_element * num ঢোকান
-
getProduct() পদ্ধতি কে ইনপুট হিসাবে গ্রহণ করবে
-
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