C++ में nth बदसूरत संख्या खोजने का कार्यक्रम

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

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

• आकार की एक सरणी v परिभाषित करें(n + 1)
• यदि n 1 के समान है, तो:
  • वापसी 1
• दो:=2, तीन:=3, पांच:=5
• twoIdx:=2, threeIdx:=2, FiveIdx:=2
• इनिशियलाइज़ i :=2 के लिए, जब i <=n, अपडेट (i 1 से बढ़ाएँ), करें:
  • curr :=कम से कम दो, तीन और पांच
  • v[i] :=curr
  • यदि curr दो के समान है, तो:
    • दो :=v[twoIdx] * 2;
    • (दो आईडीएक्स को 1 से बढ़ाएं)
  • यदि curr तीन के समान है, तो:
    • तीन :=v[threeIdx] *3
    • (3Idx को 1 से बढ़ाएं)
  • यदि curr पांच के समान है, तो:
    • पांच :=v[fiveIdx] * 5
    • (पांचIdx को 1 से बढ़ाएं)
• वापसी v[n]

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

उदाहरण

#include
using namespace std;
class Solution {
   public:
   int nthUglyNumber(int n) {
      vector 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(15));
}

इनपुट

15

आउटपुट

24