Minimum number of palindromes required to express N as a sum using C++.

Problem statement

Given a number N, we have to find the minimum number of palindromes required to express N as a sum of them

If N = 15 then 2 palindromes are required i.e. 8 and 7.

Algorithm

1. Generate all the palindromes up to N in a sorted fashion 2. Find the size of the smallest subset such that its sum is N

Example

#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; }

Output

When you compile and execute the above program. It generates the following output −

Minimum required palindromes = 2