Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सुपर अगली नंबर


हमें 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

  1. - C++ में मितव्ययी संख्या (Frugal Number)

    इस समस्या में, हमें एक धनात्मक पूर्णांक N दिया गया है। हमारा कार्य यह जांचने के लिए एक प्रोग्राम बनाना है कि दी गई संख्या मितव्ययी संख्या है या नहीं। मितव्ययी संख्या (FRUGAL NUMBER) − एक संख्या जिसके अंकों की संख्या उस संख्या के अभाज्य गुणनखंडन में अंकों की संख्या से सख्ती से अधिक है। उदाहरण &

  1. C++ में पेंटाटोप संख्या C++ में पेंटाटोप संख्या

    एक पेंटाटोप संख्या को पास्कल के त्रिभुज में पांचवीं संख्या के रूप में वर्णित किया गया है। अब, चूंकि यह पांचवीं संख्या है, इसका मतलब है कि पास्कल के त्रिभुज में कम से कम पांच संख्याएं होनी चाहिए, इसलिए इस श्रृंखला की पहली संख्या 1 4 6 4 1 से शुरू होती है जो पास्कल के त्रिभुज की चौथी पंक्ति है। तो, इस

  1. - C++ में बदसूरत संख्या

    बदसूरत संख्याएं वे संख्याएं हैं जिनके अभाज्य गुणनखंड 2, 3 या 5 हैं। 1 से 15 तक, 11 बदसूरत संख्याएं हैं: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15। संख्याएं 7, 11, 13 बदसूरत नहीं हैं क्योंकि वे अभाज्य हैं। संख्या 14 बदसूरत नहीं है क्योंकि इसके अभाज्य गुणनखंड में 7 आएगा। तो मान लीजिए हम 10वीं बदसूरत संख्या