ধরুন আমাদের nম কুৎসিত সংখ্যাটি খুঁজে বের করতে হবে, তাই আমাদের একটি পদ্ধতি নির্ধারণ করতে হবে যা এটি খুঁজে পেতে পারে। যেমন আমরা জানি যে কুৎসিত সংখ্যা হল সেই সংখ্যা, যার মৌলিক গুণনীয়ক মাত্র 2, 3 এবং 5। তাই আমরা যদি 10 তম কুৎসিত সংখ্যা বের করতে চাই, তাহলে সেটি হবে 12, যেমন প্রথম কয়েকটি কুৎসিত সংখ্যা হল 1, 2, 3, 4, 5, 6, 8, 9, 10, 12
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n + 1
আকারের একটি অ্যারে v তৈরি করুন -
যদি n =1 হয়, তাহলে 1 ফেরত দিন
-
দুই :=2, তিন =3 এবং পাঁচ =5, towIndex :=2, three Index :=2 এবং Five Index :=2
-
আমি 2 থেকে n
পরিসরে-
curr :=দুই, তিন এবং পাঁচের মিনিট
-
v[i] :=curr
-
যদি curr =দুই, তাহলে দুই :=v[twoIndex] * 2, twoIndex বাড়ান 1
-
যদি curr =তিনটি, তাহলে তিনটি :=v[threeIndex] * 3, ThreeIndex বাড়ান 1
-
যদি curr =পাঁচ, তাহলে পাঁচ :=v[fiveIndex] * 3, 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
