ন্যূনতম ফ্যাক্টরাইজেশন (Minimum Factorization) C++-এ

সমস্যা বিবরণ

একটি পজিটিভ ইন্টিজার x দেওয়া আছে। সবচেয়ে ছোট পজিটিভ ইন্টিজার b খুঁজে বের করতে হবে যাতে b-এর সব ডিজিটের গুণফল x হয়। অসম্ভব হলে ০ রিটার্ন করুন।

উদাহরণ

x = 48 → আউটপুট: 68 (৬ × ৮ = ৪৮, এবং ৬৮ ছোটতম এমন সংখ্যা)

অ্যালগরিদম: লালচী (Greedy) ফ্যাক্টরাইজেশন

1. যদি x < 2 হয়, রিটার্ন x।
2. ৯ থেকে ২ পর্যন্ত ডিজিটে ট্রাই করুন (বড় ডিজিট আগে ব্যবহার করলে কম ডিজিট লাগবে → ছোট সংখ্যা হবে)।
3. যখন x % i == 0, x /= i করুন এবং ডিজিট i আন্সারে যোগ করুন (সবচেয়ে ডানদিকে, যাতে ছোট সংখ্যা হয়)।
4. শেষে যদি x == 1 হয়, আন্সার রিটার্ন করুন, অন্যথায় ০।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;

class Solution {
public:
    int smallestFactorization(int a) {
        lli res = 0, mul = 1;
        if (a < 2) return a;
        for (lli i = 9; i >= 2; i--) {
            while (a % i == 0) {
                res = i * mul + res; // ডিজিট বামদিকে যোগ
                mul *= 10;
                a /= i;
            }
        }
        return (a < 2 && res < INT_MAX) ? (int)res : 0;
    }
};

int main() {
    Solution ob;
    cout << ob.smallestFactorization(48); // আউটপুট: 68
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(log x) — ফ্যাক্টর সংখ্যা সীমিত।
• স্থান জটিলতা: O(1) — কনস্ট্যান্ট স্পেস।