C++ এ সুপার কুৎসিত সংখ্যা

নম সুপার কুৎসিত সংখ্যাটি খুঁজে পেতে আমাদের একটি ফাংশন তৈরি করতে হবে৷ সুপার কুৎসিত সংখ্যাগুলি হল ধনাত্মক সংখ্যা যার সমস্ত মৌলিক গুণনীয়কগুলি k আকারের প্রদত্ত মৌলিক তালিকার প্রাইমগুলিতে রয়েছে। তাই যদি n হয় 12 এবং প্রাইম হয় [2, 7, 13, 19], তাহলে আউটপুট হবে 32, এর কারণ [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] হল 12টি অতি কুৎসিত সংখ্যার ক্রম৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• num, prime এবং idx

  সহ একটি ডেটা স্ট্রাকচার ট্রিপলেট তৈরি করুন

• যদি n 1 হয়, তাহলে 1 ফেরত দিন, n + 1 আকারের একটি অ্যারে তৈরি করুন এবং এটি 1 দিয়ে পূরণ করুন

• একটি অগ্রাধিকার সারি সংজ্ঞায়িত করুন pq

• আমি 0 থেকে প্রাইম-

  এর মাপ পরিসরে

  • ট্রিপলেট তৈরি করুন t(primes[i], primes[i], 2)

• আমি 2 থেকে n

  পরিসরে

  • curr :=pq এর শীর্ষ উপাদান, তারপর pq

    থেকে মুছে দিন

  • val :=curr সংখ্যা

  • v[i] :=ভাল

  • curr এর সংখ্যা :=curr এর প্রধান * v[curr এর সূচক]

  • curr এর সূচক 1 দ্বারা বৃদ্ধি করুন

  • pq

    -এ curr ঢোকান

  • while val =pq শীর্ষের সংখ্যা,

    • curr :=pq এর শীর্ষ এবং pq থেকে মুছে দিন

    • curr এর সংখ্যা :=curr এর প্রধান * v[curr এর সূচক]

    • curr এর সূচক 1 দ্বারা বৃদ্ধি করুন

    • pq

      -এ curr ঢোকান

• প্রত্যাবর্তন 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]

আউটপুট

32