C++-এ nth অগ్లీ (Ugly) সংখ্যা বের করার প্রোগ্রাম

ধরি আমাদের একটি সংখ্যা n আছে; আমাদের n-তম অগ్లీ (ugly) সংখ্যা বের করতে হবে। অগ్లీ সংখ্যা হলো যেসব সংখ্যার প্রাইম ফ্যাক্টর (prime factor) শুধু ২, ৩ এবং ৫। সুতরাং ১০ম অগ్లీ সংখ্যা বের করলে আউটপুট হবে ১২, কারণ প্রথম কয়েকটি অগլի সংখ্যা: ১, ২, ৩, ৪, ৫, ৬, ৮, ৯, ১০, ১২...।

সমাধানের ধাপসমূহ:

• সাইজ n+1 এর একটি অ্যারে v ডিফাইন করুন
• যদি n == 1 হয়, তবে: return 1
• two := 2, three := 3, five := 5
• twoIdx := 2, threeIdx := 2, fiveIdx := 2
• i := 2 থেকে i <= n পর্যন্ত লুপ চালান:
  • curr := min(two, three, five)
  • v[i] := curr
  • যদি curr == two হয়: two := v[twoIdx] * 2, twoIdx++
  • যদি curr == three হয়: three := v[threeIdx] * 3, threeIdx++
  • যদি curr == five হয়: five := v[fiveIdx] * 5, fiveIdx++
• 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));
}

ইনপুট

15

আউটপুট

24