ধরুন আমাদের একটি সংখ্যা n আছে; আমাদের nম কুৎসিত সংখ্যাটি খুঁজে বের করতে হবে। আমরা জানি যে কুৎসিত সংখ্যা হল সেই সংখ্যা, যার মৌলিক গুণনীয়ক মাত্র 2, 3 এবং 5। তাই আমরা যদি 10 th বের করতে চাই কুৎসিত সংখ্যা, আউটপুট 12 হবে, কারণ প্রথম কয়েকটি কুৎসিত সংখ্যা হল 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 এবং আরও অনেক কিছু৷
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব:
- একটি অ্যারে v আকারের (n + 1) সংজ্ঞায়িত করুন
- যদি n 1 এর মত হয়, তাহলে:
- প্রত্যাবর্তন 1
- দুই :=২, তিন :=৩, পাঁচ :=৫
- টুআইডিএক্স :=২, থ্রিআইডিএক্স :=২, ফাইভআইডিএক্স :=২
- আরম্ভ করার জন্য i :=2, যখন i <=n, আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), করুন:
- curr :=ন্যূনতম দুই, তিন এবং পাঁচ
- v[i] :=curr
- যদি curr দুইটির সমান হয়, তাহলে:
- দুই :=v[twoIdx] * 2;
- (1 দ্বারা twoIdx বাড়ান)
- যদি curr তিনটির সমান হয়, তাহলে:
- তিন :=v[threeIdx] * 3
- (3Idx 1 দ্বারা বৃদ্ধি করুন)
- যদি curr পাঁচটির সমান হয়, তাহলে:
- পাঁচ :=v[fiveIdx] * 5
- (ফাইভআইডিএক্স 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
