हमें nवें सुपर अगली नंबर को ढूंढने के लिए एक फंक्शन बनाना है। सुपर अगली नंबर वे पॉजिटिव नंबर हैं जिनके सभी प्राइम फैक्टर दिए गए प्राइम लिस्ट primes में हैं जिसका आकार k है। यदि n 12 है और primes [2, 7, 13, 19] हैं, तो आउटपुट 32 होगा, ऐसा इसलिए क्योंकि [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] 12 सुपर अगली नंबर्स का अनुक्रम है।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- num, प्राइम और idx के साथ ट्रिपलेट नामक एक डेटा स्ट्रक्चर बनाएं
- यदि n 1 है, तो 1 लौटाएं, n + 1 आकार का एक ऐरे बनाएं, और इसे 1 से भरें
- pq नामक एक प्रायोरिटी क्यू परिभाषित करें
- i के लिए 0 से primes के आकार - 1 तक की रेंज में
- ट्रिपलेट्स t(primes[i], primes[i], 2) बनाएं
- i के लिए 2 से n तक की रेंज में
- करंट := pq का टॉप एलिमेंट, फिर pq से डिलीट करें
- वैल := करंट का num
- v[i] := वैल
- करंट का num := करंट का प्राइम * v[करंट का इंडेक्स]
- करंट के इंडेक्स को 1 से बढ़ाएं
- करंट को pq में डालें
- जब तक वैल = pq टॉप का num,
- करंट := pq का टॉप और pq से डिलीट करें
- करंट का num := करंट का प्राइम * v[करंट का इंडेक्स]
- करंट के इंडेक्स को 1 से बढ़ाएं
- करंट को 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]
आउटपुट
32