मान लीजिए हमें nth बदसूरत संख्या ढूंढनी है, इसलिए हमें एक विधि परिभाषित करनी है जो इसे ढूंढ सके। जैसा कि हम जानते हैं कि बदसूरत संख्याएं वे संख्याएं हैं जिनके अभाज्य गुणनखंड केवल 2, 3 और 5 हैं।
उदाहरण के लिए, यदि हम 10वीं बदसूरत संख्या ढूंढना चाहते हैं, तो वह 12 होगी, क्योंकि पहली कुछ बदसूरत संख्याएं 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 हैं।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
vनामक एक सरणी बनाएं, आकारn + 1का- यदि
n = 1, तो 1 लौटाएं two := 2,three = 3औरfive = 5,twoIndex := 2,threeIndex := 2औरfiveIndex := 2iको 2 सेnतक लूप करेंcurr := two, three और five का न्यूनतमv[i] := curr- यदि
curr = two, तोtwo := v[twoIndex] * 2,twoIndexको 1 से बढ़ाएं - यदि
curr = three, तोthree := v[threeIndex] * 3,threeIndexको 1 से बढ़ाएं - यदि
curr = five, तोfive := v[fiveIndex] * 5,fiveIndexको 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