Minimum palindromes needed to express a number as a sum

Updated

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

Examples :

Input : N = 11
Output : [ 11 ]
Explanation :
11 is itself a palindrome.

Input : N = 65
Output : [55, 9, 1]
Explanation :
65 can be expressed as a sum of three palindromes (55, 9, 1).

Approach :

The problem can also be solved using  largest  palindrome number lesser than or equal to given number. In this approach we find the largest palindrome number lesser than or equal to given number and then subtract that number from the given number. And then again find the largest palindrome for the rest value left. This process goes until the rest value becomes equal to a single digit number.

A table of greedy steps for 65 that take 55, 9 and 1 in turn and leave 10, 1 and 0, so three palindromes add up to 65.

Implementation :

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

// A utility function to check if number is power of 10
bool Check(string s, int n)
{
    if (s[0] == '1') {
        for (int i = 1; i < n; i++) {
            if (s[i] != '0')
                return false;
        }
        return true;
    }
    return false;
}

// This function is to find the largest palindrome lesser
// than the number s
string generatePrevPalindrome(string s, int n)
{

    // Input type 1: If number is power of 10
    // simply o/p 9 n-1 times
    if (Check(s, n)) {
        string res;
        for (int i = 1; i < n; i++)
            res.push_back('9');
        return res;
    }

    // For input type 2 and type 3

    // find the index of mid digit
    int mid = n / 2;

    // A bool variable to check if copy of left side to
    // right is sufficient or not
    bool leftlarger = false;

    // end of left side pointer is always 'mid -1'
    int i = mid - 1;

    // Beginning of right side pointer depends if n is odd
    // or even
    int j = (n % 2) ? mid + 1 : mid;

    // Initially, ignoring  the middle same digits
    while (i >= 0 && s[i] == s[j])
        i--, j++;

    // If the string is palindrome itself
    // then return the string
    if (i < 0)
        return s;

    // Find if the middle digit(s) need to be decrmented or
    // not (or copying left side is not sufficient)
    if (s[i] > s[j]) {
        // if leftlarger becomes true it means
        // we need to decrement middle elements
        leftlarger = true;
    }

    // Copy the mirror of left to right
    while (i >= 0) {
        s[j] = s[i];
        j++;
        i--;
    }

    // Handle the case where middle digit(s) must be
    // decremented . This part of code is for CASE 1 and
    // CASE 2.2
    if (leftlarger == true) {
        i = mid - 1;
        int borrow = 1;
        // If there are odd digits, then decrement
        // the middle digit and store the borrow
        if (n % 2 == 1) {

            if (s[mid] == '0') {

                // If middle element is zero ,then
                // update the borrow value and middle digit
                borrow = 1;
                s[mid] = '9';
            }
            else {

                borrow = 0;
                s[mid] = s[mid] - 1;
            }
            j = mid + 1;
        }
        else {
            j = mid;
        }

        // Subtract 1 to the rightmost digit of the left
        // side, propagate the borrow towards MSB digit and
        // simultaneously copying mirror of the left side to
        // the right side.
        while (i >= 0) {
            if (borrow == 1) {
                if (s[i] == '0') {
                    // If i th digit  element is zero ,then
                    // update the borrow value and middle
                    // digit
                    borrow = 1;
                    s[i] = '9';
                }
                else {
                    borrow = 0;
                    s[i] = s[i] - 1;
                }
            }
            // copy mirror to right
            s[j++] = s[i--];
        }
    }
    return s;
}

// Driver Program to test above function
int main()
{
    // Given number
    int num = 100;

    vector<string> subset;

    while (num >= 10) {
        // Change the number into string format
        string s = to_string(num);

        // length of string 
        int n = s.length();

        // Finding the largest palindrome lesser than given
        // number
        string pal = generatePrevPalindrome(s, n);

        // storing in vector subset
        subset.push_back(pal);

        // Change the string into number format
        int pal_num = stoi(pal);
      	
      	// Process left for rest value 
        num = num - pal_num;
    }
    if (num != 0) {
        subset.push_back(to_string(num));
    }

    for (int i = 0; i < subset.size(); i++) {
        cout << subset[i] << " ";
    }
    return 0;
}

Time Complexity : O(n) where n is length of number

Comment
Next tutorial
Mithlesh Upadhyay Published 21 Nov 2026 · 4 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials