C++ में nth Ugly Number ढूंढने वाला प्रोग्राम

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

समाधान दृष्टिकोण

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

1. आकार (n + 1) का एक सरणी v परिभाषित करें।
2. यदि n 1 के समान है, तो:
   • 1 लौटाएँ
3. two := 2, three := 3, five := 5
4. twoIdx := 2, threeIdx := 2, fiveIdx := 2
5. i := 2 से आरंभ करें, जब i <= n, अपडेट करें (i को 1 से बढ़ाएँ), करें:
   • curr := two, three, और five का न्यूनतम
   • v[i] := curr
   • यदि curr two के समान है, तो:
     • two := v[twoIdx] * 2
     • twoIdx को 1 से बढ़ाएँ
   • यदि curr three के समान है, तो:
     • three := v[threeIdx] * 3
     • threeIdx को 1 से बढ़ाएँ
   • यदि curr five के समान है, तो:
     • five := v[fiveIdx] * 5
     • fiveIdx को 1 से बढ़ाएँ
6. v[n] लौटाएँ

उदाहरण

#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];
    }
};

int main() {
    Solution ob;
    cout << (ob.nthUglyNumber(15));
    return 0;
}

इनपुट

15

आउटपुट

24