C++ ব্যবহার করে N কে প্যালিনড্রোম সংখ্যাগুলোর যোগফল হিসেবে প্রকাশের ন্যূনতম প্যালিনড্রোম সংখ্যা

সমস্যা বিবরণ

একটি সংখ্যা N দেওয়া আছে। N কে প্যালিনড্রোম সংখ্যাগুলোর যোগফল হিসেবে প্রকাশের জন্য ন্যূনতম কতগুলো প্যালিনড্রোম সংখ্যা লাগবে তা বের করতে হবে।

যদি N = 15 হয়, তবে ২টি প্যালিনড্রোম সংখ্যা দরকার: ৮ এবং ৭।

এলগরিদম

1. N পর্যন্ত সব প্যালিনড্রোম সংখ্যা জেনারেট করুন সর্টেড ফ্যাশনে
2. সবচেয়ে ছোট সাবসেটের আকার বের করুন যার যোগফল N হবে

উদাহরণ কোড

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

vector<vector<long long>> table;

int createPalindrome(int input, bool isOdd) {
    int n = input;
    int palindrome = input;
    if (isOdd)
        n /= 10;
    while (n > 0) {
        palindrome = palindrome * 10 + (n % 10);
        n /= 10;
    }
    return palindrome;
}

vector<int> generatePalindromes(int n) {
    vector<int> palindromes;
    int number;
    for (int j = 0; j < 2; j++) {
        int i = 1;
        while ((number = createPalindrome(i++, j)) <= n)
            palindromes.push_back(number);
    }
    return palindromes;
}

long long minSubsetSize(vector<int>& vec, int i, int j, int n) {
    if (n == 0)
        return 0;
    if (i > j || vec[i] > n)
        return INT_MAX;
    if (table[i][n])
        return table[i][n];
    table[i][n] = min(1 + minSubsetSize(vec, i + 1, j, n - vec[i]), minSubsetSize(vec, i + 1, j, n));
    return table[i][n];
}

int requiredPalindromes(int n) {
    vector<int> palindromes = generatePalindromes(n);
    sort(palindromes.begin(), palindromes.end());
    table = vector<vector<long long>>(palindromes.size(), vector<long long>(n + 1, 0));
    return minSubsetSize(palindromes, 0, palindromes.size() - 1, n);
}

int main() {
    int n = 15;
    cout << "Minimum required palindromes = " << requiredPalindromes(n) << endl;
    return 0;
}

আউটপুট

প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে:

Minimum required palindromes = 2