समस्या कथन
एक संख्या N दी गई है, हमें N को पालिंड्रोम के योग के रूप में व्यक्त करने के लिए आवश्यक न्यूनतम पालिंड्रोम की संख्या ढूंढनी है।
यदि N=15, तो 2 पालिंड्रोम आवश्यक हैं: 8 और 7।
एल्गोरिदम
1. N तक के सभी पालिंड्रोम को सॉर्टेड तरीके से उत्पन्न करें 2. सबसे छोटे सबसेट का आकार ढूंढें जिसका योग N हो
C++ उदाहरण
#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, 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