सी ++ में बदसूरत संख्या II

मान लीजिए हमें nth बदसूरत संख्या का पता लगाना है, इसलिए हमें एक ऐसी विधि को परिभाषित करना होगा जो इसे ढूंढ सके। जैसा कि हम जानते हैं कि कुरूप संख्याएँ वे संख्याएँ होती हैं, जिनके अभाज्य गुणनखंड केवल 2, 3 और 5 होते हैं। इसलिए यदि हम 10वीं कुरूप संख्या ज्ञात करना चाहते हैं, तो वह 12 होगी, क्योंकि पहली कुछ कुरूप संख्याएँ 1, 2, 3 हैं। 4, 5, 6, 8, 9, 10, 12

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• आकार n + 1

  . का एक सरणी v बनाएं

• अगर n =1 है, तो 1 लौटाएं

• दो:=2, तीन =3 और पांच =5, टो इंडेक्स:=2, थ्रीइंडेक्स:=2 और फाइवइंडेक्स:=2

• मेरे लिए 2 से n की सीमा में

  • curr :=दो, तीन और पांच का मिनट

  • v[i] :=कर्व

  • अगर curr =दो, तो दो :=v[twoIndex] * 2, दो इंडेक्स को 1 से बढ़ाएं

  • अगर curr =तीन, तो तीन :=v[threeIndex] * 3, तीन इंडेक्स को 1 से बढ़ाएं

  • अगर curr =पाँच, तो पाँच :=v[fiveIndex] * 3, पाँच इंडेक्स को 1 से बढ़ाएँ

• वापसी v[n]

उदाहरण(C++)

आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int nthUglyNumber(int n) {
      vector <int> v(n + 1);
      if(n == 1){
         return 1;
      }
      int two = 2, three = 3, five = 5;
      int twoIdx = 2;
      int threeIdx = 2;
      int fiveIdx = 2;
      for(int i = 2; i <= n; i++){
         int curr = min({two, three, five});
         v[i] = curr;
         if(curr == two){
            two = v[twoIdx] * 2;;
            twoIdx++;
         }
         if(curr == three){
            three = v[threeIdx] * 3;
            threeIdx++;
         }
         if(curr == five){
            five = v[fiveIdx] * 5;
            fiveIdx++;
         }
      }
      return v[n];
   }
};
main(){
   Solution ob;
   cout << (ob.nthUglyNumber(10));
}

इनपुट

10

आउटपुट

12