C++-এ সুপার আгли নাম্বার

আমাদের nth সুপার আгли নাম্বার বের করার একটি ফাংশন তৈরি করতে হবে। সুপার আгли নাম্বার হলো ধনাত্মক সংখ্যাগুলো যাদের সব প্রাইম ফ্যাক্টর দেওয়া প্রাইম লিস্ট `primes` (আকার k) এ থাকে। যদি `n` = 12 এবং `primes` = [2, 7, 13, 19] হয়, তবে আউটপুট হবে ৩২, কারণ [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] হলো ১২টি সুপার আгли নাম্বারের সিকোয়েন্স।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -

`triplet` নামক একটি ডেটা স্ট্রাকচার তৈরি করুন, যার `num`, `prime` এবং `idx` থাকবে
যদি `n` ১ হয়, তবে ১ রিটার্ন করুন, আকার `n + 1` একটি অ্যারে তৈরি করুন এবং ১ দিয়ে ফিল করুন
একটি প্রায়োরিটি কিউ `pq` সংজ্ঞায়িত করুন
`i` = 0 থেকে `primes`-এর আকার - 1 পর্যন্ত
- `triplet` t(`primes[i]`, `primes[i]`, 2) তৈরি করুন
`i` = 2 থেকে `n` পর্যন্ত
- `curr := pq`-এর টপ এলিমেন্ট, তারপর `pq`-থেকে ডিলিট করুন
- `val := curr`-এর `num`
- `v[i] := val`
- `curr`-এর `num := curr`-এর `prime` * `v[curr.idx]`
- `curr`-এর `idx` ১ বাড়ান
- `curr`-কে `pq`-তে ইনসার্ট করুন
- যখন `val == pq.top().num`,
  - `curr := pq.top()` এবং `pq`-থেকে ডিলিট করুন
  - `curr.num := curr.prime * v[curr.idx]`
  - `curr.idx` ১ বাড়ান
  - `curr`-কে `pq`-তে ইনসার্ট করুন
`v[n]` রিটার্ন করুন

উদাহরণ (C++)

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন -

#include <bits/stdc++.h> using namespace std; struct Data{    int num, prime, idx;    Data(int a, int b, int c){       num = a;       prime = b;       idx = c;    } }; struct Comparator{    bool operator()(Data a, Data b){       return !(a.num < b.num);    } }; class Solution {    public:    int nthSuperUglyNumber(int n, vector<int>& primes) {       if(n == 1)return 1;       vector <int> v(n + 1, 1);       priority_queue < Data, vector < Data >, Comparator > pq;       for(int i = 0; i < primes.size(); i++){          pq.push(Data(primes[i], primes[i], 2));       }       int x;       for(int i = 2; i <= n; i++){          Data curr = pq.top();          pq.pop();          int val = curr.num;          v[i] = val;          curr.num = curr.prime * v[curr.idx];          curr.idx++;          pq.push(curr);          while(val == pq.top().num){             curr = pq.top();             pq.pop();             curr.num = curr.prime * v[curr.idx];             curr.idx++;             pq.push(curr);          }       }       return v[n];    } }; main(){    Solution ob;    vector<int> v = {2,7,13,19};    cout << (ob.nthSuperUglyNumber(12, v)); }

ইনপুট

12 [2,7,13,19]