Horje
Minimum number of palindromes required to express N as a sum | Set 1

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

Input: N = 11 
Output: 1 
11 is itself a palindrome.
Input: N = 65 
Output: 3 
65 can be expressed as a sum of three palindromes (55, 9, 1).

 

Approach: 
We can use Dynamic Programming to solve this problem. The idea is to first generate all the palindromes up to N in a sorted fashion, and then we can treat this problem as a variation of the subset sum problem, where we have to find the size of the smallest subset such that its sum is N.

Below is the implementation of above approach: 

CPP

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Declaring the DP table as global variable
vector<vector<long long> > dp;
 
 
// A utility for creating palindrome
int createPalindrome(int input, bool isOdd)
{
    int n = input;
    int palin = input;
 
    // checks if number of digits is odd or even
    // if odd then neglect the last digit of input in
    // finding reverse as in case of odd number of
    // digits middle element occur once
    if (isOdd)
        n /= 10;
 
    // Creates palindrome by just appending reverse
    // of number to itself
    while (n > 0) {
        palin = palin * 10 + (n % 10);
        n /= 10;
    }
 
    return palin;
}
 
// Function to generate palindromes
vector<int> generatePalindromes(int N)
{
    vector<int> palindromes;
    int number;
 
    // Run two times for odd and even length palindromes
    for (int j = 0; j < 2; j++) {
        // Creates palindrome numbers with first half as i.
        // Value of j decides whether we need an odd length
        // or even length palindrome.
        int i = 1;
        while ((number = createPalindrome(i++, j)) <= N)
            palindromes.push_back(number);
    }
 
    return palindromes;
}
 
// Function to find the minimum
// number of elements in a sorted
// array A[i..j] such that their sum is N
long long minimumSubsetSize(vector<int>& A, int i, int j, int N)
{
    if (!N)
        return 0;
 
    if (i > j || A[i] > N)
        return INT_MAX;
 
    if (dp[i][N])
        return dp[i][N];
 
    dp[i][N] = min(1 + minimumSubsetSize(A, i + 1, j,
                                         N - A[i]),
                   minimumSubsetSize(A, i + 1, j, N));
 
    return dp[i][N];
}
 
// Function to find the minimum
// number of palindromes that N
// can be expressed as a sum of
int minimumNoOfPalindromes(int N)
{
    // Getting the list of all palindromes upto N
    vector<int> palindromes = generatePalindromes(N);
 
    // Sorting the list of palindromes
    sort(palindromes.begin(), palindromes.end());
 
    // Initializing the DP table
    dp = vector<vector<long long> >(palindromes.size(),
                                    vector<long long>(N + 1, 0));
 
    // Returning the required value
    return minimumSubsetSize(palindromes, 0,
                             palindromes.size() - 1, N);
}
 
// Driver code
int main()
{
    int N = 65;
    cout << minimumNoOfPalindromes(N);
    return 0;
}

Java

/*package whatever //do not write package name here */
 
import java.io.*;
import java.util.*;
 
class GFG {
  // Java implementation of above approach
 
  // Declaring the DP table as global variable
  static long[][] dp;
 
 
  // A utility for creating palindrome
  static int createPalindrome(int input, int isOdd)
  {
    int n = input;
    int palin = input;
 
    // checks if number of digits is odd or even
    // if odd then neglect the last digit of input in
    // finding reverse as in case of odd number of
    // digits middle element occur once
    if (isOdd > 0)
      n /= 10;
 
    // Creates palindrome by just appending reverse
    // of number to itself
    while (n > 0) {
      palin = palin * 10 + (n % 10);
      n /= 10;
    }
 
    return palin;
  }
 
  // Function to generate palindromes
  static ArrayList<Integer> generatePalindromes(int N)
  {
    ArrayList<Integer> palindromes = new ArrayList<>();
    int number;
 
    // Run two times for odd and even length palindromes
    for (int j = 0; j < 2; j++) {
      // Creates palindrome numbers with first half as i.
      // Value of j decides whether we need an odd length
      // or even length palindrome.
      int i = 1;
      while ((number = createPalindrome(i++, j)) <= N)
        palindromes.add(number);
    }
 
    return palindromes;
  }
 
  // Function to find the minimum
  // number of elements in a sorted
  // array A[i..j] such that their sum is N
  static long minimumSubsetSize(ArrayList<Integer> A, int i, int j, int N)
  {
    if (N == 0)
      return 0;
 
    if (i > j || A.get(i) > N)
      return Integer.MAX_VALUE;
 
    if (dp[i][N] > 0)
      return dp[i][N];
 
    dp[i][N] = Math.min(1 + minimumSubsetSize(A, i + 1, j,
                                              N - A.get(i)),
                        minimumSubsetSize(A, i + 1, j, N));
 
    return dp[i][N];
  }
 
  // Function to find the minimum
  // number of palindromes that N
  // can be expressed as a sum of
  static int minimumNoOfPalindromes(int N)
  {
    // Getting the list of all palindromes upto N
    ArrayList<Integer> palindromes = generatePalindromes(N);
 
    // Sorting the list of palindromes
    Collections.sort(palindromes);
 
    // Initializing the DP table
    dp = new long [palindromes.size()][N + 1];
 
 
 
    // Returning the required value
    return (int)minimumSubsetSize(palindromes, 0,
                                  palindromes.size() - 1, N);
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int N = 65;
    System.out.println(minimumNoOfPalindromes(N));
  }
}
 
// This code is contributed by shinjanpatra.

Python3

# Python3 implementation of above approach
 
# Declaring the DP table as global variable
dp = [[0 for i in range(1000)] for i in range(1000)]
 
# A utility for creating palindrome
def createPalindrome(input, isOdd):
 
    n = input
    palin = input
 
    # checks if number of digits is odd or even
    # if odd then neglect the last digit of input in
    # finding reverse as in case of odd number of
    # digits middle element occur once
    if (isOdd):
        n //= 10
 
    # Creates palindrome by just appending reverse
    # of number to itself
    while (n > 0):
        palin = palin * 10 + (n % 10)
        n //= 10
 
    return palin
 
# Function to generate palindromes
def generatePalindromes(N):
 
    palindromes = []
    number = 0
 
    # Run two times for odd and even length palindromes
    for j in range(2):
         
        # Creates palindrome numbers with first half as i.
        # Value of j decides whether we need an odd length
        # or even length palindrome.
        i = 1
        number = createPalindrome(i, j)
        while number <= N:
            number = createPalindrome(i, j)
            palindromes.append(number)
            i += 1
 
    return palindromes
 
# Function to find the minimum
# number of elements in a sorted
# array A[i..j] such that their sum is N
def minimumSubsetSize(A, i, j, N):
 
    if (not N):
        return 0
 
    if (i > j or A[i] > N):
        return 10**9
 
    if (dp[i][N]):
        return dp[i][N]
 
    dp[i][N] = min(1 + minimumSubsetSize(A, i + 1, j, N - A[i]),
                    minimumSubsetSize(A, i + 1, j, N))
 
    return dp[i][N]
 
# Function to find the minimum
# number of palindromes that N
# can be expressed as a sum of
def minimumNoOfPalindromes(N):
 
    # Getting the list of all palindromes upto N
    palindromes = generatePalindromes(N)
 
    # Sorting the list of palindromes
    palindromes = sorted(palindromes)
 
    # Returning the required value
    return minimumSubsetSize(palindromes, 0, len(palindromes) - 1, N)
 
# Driver code
N = 65
print(minimumNoOfPalindromes(N))
 
# This code is contributed by mohit kumar 29

C#

// C# program to implement the approach
using System;
using System.Collections.Generic;
 
class GFG {
 
  // Declaring the DP table as global variable
  static long[, ] dp;
 
  // A utility for creating palindrome
  static int createPalindrome(int input, int isOdd)
  {
    int n = input;
    int palin = input;
 
    // checks if number of digits is odd or even
    // if odd then neglect the last digit of input in
    // finding reverse as in case of odd number of
    // digits middle element occur once
    if (isOdd > 0)
      n /= 10;
 
    // Creates palindrome by just appending reverse
    // of number to itself
    while (n > 0) {
      palin = palin * 10 + (n % 10);
      n /= 10;
    }
 
    return palin;
  }
 
  // Function to generate palindromes
  static List<int> generatePalindromes(int N)
  {
    List<int> palindromes = new List<int>();
    int number;
 
    // Run two times for odd and even length palindromes
    for (int j = 0; j < 2; j++) {
      // Creates palindrome numbers with first half as
      // i. Value of j decides whether we need an odd
      // length or even length palindrome.
      int i = 1;
      while ((number = createPalindrome(i++, j)) <= N)
        palindromes.Add(number);
    }
 
    return palindromes;
  }
 
  // Function to find the minimum
  // number of elements in a sorted
  // array A[i..j] such that their sum is N
  static long minimumSubsetSize(List<int> A, int i, int j,
                                int N)
  {
    if (N == 0)
      return 0;
 
    if (i > j || A[i] > N)
      return Int32.MaxValue;
 
    if (dp[i, N] > 0)
      return dp[i, N];
 
    dp[i, N] = Math.Min(
      1 + minimumSubsetSize(A, i + 1, j, N - A[i]),
      minimumSubsetSize(A, i + 1, j, N));
 
    return dp[i, N];
  }
 
  // Function to find the minimum
  // number of palindromes that N
  // can be expressed as a sum of
  static int minimumNoOfPalindromes(int N)
  {
    // Getting the list of all palindromes upto N
    List<int> palindromes = generatePalindromes(N);
 
    // Sorting the list of palindromes
    palindromes.Sort();
 
    // Initializing the DP table
    dp = new long[palindromes.Count, N + 1];
 
    // Returning the required value
    return (int)minimumSubsetSize(
      palindromes, 0, palindromes.Count - 1, N);
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    int N = 65;
    Console.WriteLine(minimumNoOfPalindromes(N));
  }
}
 
// This code is contributed by phasing17.

Javascript

<script>
 
// JavaScript implementation of above approach
 
// Declaring the DP table as global variable
let dp = new Array(1000);
for(let i = 0; i < 1000; i++)
{
    dp[i] = new Array(1000).fill(0);
}
 
// A utility for creating palindrome
function createPalindrome(input, isOdd){
 
    let n = input
    let palin = input
 
    // checks if number of digits is odd or even
    // if odd then neglect the last digit of input in
    // finding reverse as in case of odd number of
    // digits middle element occur once
    if (isOdd)
        n = Math.floor(n /10)
 
    // Creates palindrome by just pushing reverse
    // of number to itself
    while (n > 0){
        palin = palin * 10 + (n % 10)
        n = Math.floor(n /10)
    }
 
    return palin
}
 
// Function to generate palindromes
function generatePalindromes(N){
 
    let palindromes = []
    let number = 0
 
    // Run two times for odd and even length palindromes
    for(let j = 0; j < 2; j++)
    {
         
        // Creates palindrome numbers with first half as i.
        // Value of j decides whether we need an odd length
        // or even length palindrome.
        let i = 1
        number = createPalindrome(i, j)
        while(number <= N){
            number = createPalindrome(i, j)
            palindromes.push(number)
            i += 1
        }
    }
 
    return palindromes
}
 
// Function to find the minimum
// number of elements in a sorted
// array A[i..j] such that their sum is N
function minimumSubsetSize(A, i, j, N){
 
    if (N == 0)
        return 0
 
    if (i > j || A[i] > N)
        return Math.pow(10,9)
 
    if (dp[i][N])
        return dp[i][N]
 
    dp[i][N] = Math.min(1 + minimumSubsetSize(A, i + 1, j, N - A[i]),
                    minimumSubsetSize(A, i + 1, j, N))
 
    return dp[i][N]
}
 
// Function to find the minimum
// number of palindromes that N
// can be expressed as a sum of
function minimumNoOfPalindromes(N){
 
    // Getting the list of all palindromes upto N
    let palindromes = generatePalindromes(N)
 
    // Sorting the list of palindromes
    palindromes.sort((a,b)=>a-b)
 
    // Returning the required value
    return minimumSubsetSize(palindromes, 0, palindromes.length - 1, N)
}
 
// Driver code
let N = 65
document.write(minimumNoOfPalindromes(N),"</br>")
 
// This code is contributed by shinjanpatra
 
</script>

Output

3

Efficient approach : Using DP Tabulation method ( Iterative approach )

Implementation :

C++

#include <bits/stdc++.h>
using namespace std;
 
vector<vector<long long>> dp;
 
// A utility for creating palindrome
int createPalindrome(int input, bool isOdd) {
    int n = input;
    int palin = input;
 
    // checks if number of digits is odd or even
    // if odd then neglect the last digit of input in
    // finding reverse as in case of odd number of
    // digits middle element occur once
    if (isOdd)
        n /= 10;
     
    // Creates palindrome by just appending reverse
    // of number to itself
    while (n > 0) {
        palin = palin * 10 + (n % 10);
        n /= 10;
    }
 
    return palin;
}
 
// Function to generate palindromes
vector<int> generatePalindromes(int N) {
    vector<int> palindromes;
    int number;
 
    // Run two times for odd and even length palindromes
    for (int j = 0; j < 2; j++) {
        int i = 1;
        while ((number = createPalindrome(i++, j)) <= N)
            palindromes.push_back(number);
    }
     
    return palindromes;
}
 
 
// Function to find the minimum
// number of elements in a sorted
// array A[i..j] such that their sum is N
long long minimumSubsetSize(vector<int>& A, int N) {
    int n = A.size();  
     
    // intialize
    dp = vector<vector<long long>>(n + 1, vector<long long>(N + 1, 0));
     
    // initialize base case
    for (int i = 0; i <= n; i++)
        dp[i][0] = 0;
 
    for (int j = 1; j <= N; j++)
        dp[0][j] = INT_MAX;
     
    // iterate over DP to get the current value from previous computation
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= N; j++) {
            if (A[i - 1] > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = min(1 + dp[i - 1][j - A[i - 1]], dp[i - 1][j]);
        }
    }
     
    //return final answer stored in DP
    return dp[n][N];
}
 
// Function to find the minimum
// number of palindromes that N
// can be expressed as a sum of
int minimumNoOfPalindromes(int N) {
     
    // Getting the list of all palindromes upto N
    vector<int> palindromes = generatePalindromes(N);
     
    // Sorting the list of palindromes
    sort(palindromes.begin(), palindromes.end());
     
     // Returning the required value
    return minimumSubsetSize(palindromes, N);
}
     
// Driver Code
int main() {
    int N = 65;
    cout << minimumNoOfPalindromes(N);
    return 0;
}

Java

import java.util.HashMap;
import java.util.Map;
 
public class MinimumPalindromes {
    static Map<Long, Long> memo = new HashMap<>();
 
    static long createPalindrome(long input, boolean isOdd) {
        long n = input;
        long palin = input;
 
        if (isOdd)
            n /= 10;
 
        while (n > 0) {
            palin = palin * 10 + (n % 10);
            n /= 10;
        }
 
        return palin;
    }
 
    static long minimumNumberOfPalindromes(long N) {
        if (N == 0) {
            return 0;
        }
 
        if (memo.containsKey(N)) {
            return memo.get(N);
        }
 
        long result = Long.MAX_VALUE;
 
        for (int i = 1; ; i++) {
            long palindrome = createPalindrome(i, true);
            if (palindrome <= N) {
                result = Math.min(result, 1 + minimumNumberOfPalindromes(N - palindrome));
            } else {
                break;
            }
        }
 
        for (int i = 1; ; i++) {
            long palindrome = createPalindrome(i, false);
            if (palindrome <= N) {
                result = Math.min(result, 1 + minimumNumberOfPalindromes(N - palindrome));
            } else {
                break;
            }
        }
 
        memo.put(N, result);
        return result;
    }
 
    public static void main(String[] args) {
        long N = 65;
        System.out.println(minimumNumberOfPalindromes(N));
    }
}

Python3

# Initialize a 2D array dp to store the minimum subset sizes
# dp[i][j] represents the minimum subset size to get a sum of j
# using the first i elements of the input array A.
dp = []
 
# A utility function to create palindromes
def create_palindrome(input_num, is_odd):
    num = input_num
    palindrome = input_num
 
    # Check if the number of digits is odd or even
    # If it's odd, neglect the last digit in finding the reverse
    if is_odd:
        num //= 10
 
    # Create a palindrome by appending the reverse of the number to itself
    while num > 0:
        palindrome = palindrome * 10 + (num % 10)
        num //= 10
 
    return palindrome
 
# Function to generate palindromes up to N
def generate_palindromes(N):
    palindromes = []
     
    # Run two times for odd and even length palindromes
    for j in range(2):
        i = 1
        while True:
            number = create_palindrome(i, j)
            if number <= N:
                palindromes.append(number)
                i += 1
            else:
                break
     
    return palindromes
 
# Function to find the minimum number of elements in a sorted
# array A[i..j] such that their sum is N
def minimum_subset_size(A, N):
    n = len(A)
     
    # Initialize dp
    dp = [[0] * (N + 1) for _ in range(n + 1)]
 
    # Initialize base case
    for i in range(n + 1):
        dp[i][0] = 0
 
    for j in range(1, N + 1):
        dp[0][j] = 10 ** 18
     
    # Iterate over DP to calculate the current value from previous computation
    for i in range(1, n + 1):
        for j in range(1, N + 1):
            if A[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = min(1 + dp[i - 1][j - A[i - 1]], dp[i - 1][j])
     
    # Return the final answer stored in DP
    return dp[n][N]
 
# Function to find the minimum number of palindromes that N
# can be expressed as a sum of
def minimum_no_of_palindromes(N):
    # Get the list of all palindromes up to N
    palindromes = generate_palindromes(N)
 
    # Sort the list of palindromes
    palindromes.sort()
 
    # Return the required value
    return minimum_subset_size(palindromes, N)
 
# Driver Code
if __name__ == "__main__":
    N = 65
    print(minimum_no_of_palindromes(N))

C#

using System;
using System.Collections.Generic;
 
public class MinimumPalindromes
{
    static List<List<long>> dp;
 
    // A utility for creating a palindrome
    static long CreatePalindrome(long input, bool isOdd)
    {
        long n = input;
        long palin = input;
 
        // Check if the number of digits is odd or even
        // If odd, then neglect the last digit of the input
        // in finding the reverse, as in the case of an odd
        // number of digits, the middle element occurs only once.
        if (isOdd)
            n /= 10;
 
        // Create a palindrome by appending the reverse of the number to itself
        while (n > 0)
        {
            palin = palin * 10 + (n % 10);
            n /= 10;
        }
 
        return palin;
    }
 
    // Function to generate palindromes
    static List<long> GeneratePalindromes(long N)
    {
        List<long> palindromes = new List<long>();
        long number;
 
        // Run two times for odd and even length palindromes
        for (int j = 0; j < 2; j++)
        {
            long i = 1;
            while ((number = CreatePalindrome(i++, j == 0)) <= N)
                palindromes.Add(number);
        }
 
        return palindromes;
    }
 
    // Function to find the minimum number of elements in a sorted
    // array A[i..j] such that their sum is N
    static long MinimumSubsetSize(List<long> A, long N)
    {
        int n = A.Count;
 
        // Initialize DP array
        dp = new List<List<long>>(n + 1);
        for (int i = 0; i <= n; i++)
            dp.Add(new List<long>(new long[N + 1]));
 
        // Initialize base case
        for (int i = 0; i <= n; i++)
            dp[i][0] = 0;
 
        for (int j = 1; j <= N; j++)
            dp[0][j] = int.MaxValue;
 
        // Iterate over DP to compute the current value from previous computation
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (A[i - 1] > j)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = Math.Min(1 + dp[i - 1][j - (int)A[i - 1]], dp[i - 1][j]);
            }
        }
 
        // Return the final answer stored in DP
        return dp[n][(int)N];
    }
 
    // Function to find the minimum number of palindromes that N
    // can be expressed as a sum of
    static long MinimumNumberOfPalindromes(long N)
    {
        // Get the list of all palindromes up to N
        List<long> palindromes = GeneratePalindromes(N);
 
        // Sort the list of palindromes
        palindromes.Sort();
 
        // Return the required value
        return MinimumSubsetSize(palindromes, N);
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        long N = 65;
        Console.WriteLine(MinimumNumberOfPalindromes(N));
    }
}

Javascript

// A utility for creating palindrome
function createPalindrome(input, isOdd) {
    let n = input;
    let palin = input;
 
    // Check if the number of digits is odd or even
    // If odd, then neglect the last digit of the input in
    // finding reverse, as in the case of an odd number of
    // digits, the middle element occurs once
    if (isOdd)
        n = Math.floor(n / 10);
 
    // Create a palindrome by just appending the reverse
    // of the number to itself
    while (n > 0) {
        palin = palin * 10 + (n % 10);
        n = Math.floor(n / 10);
    }
 
    return palin;
}
 
// Function to generate palindromes
function generatePalindromes(N) {
    const palindromes = [];
    let number;
 
    // Run two times for odd and even length palindromes
    for (let j = 0; j < 2; j++) {
        let i = 1;
        while ((number = createPalindrome(i++, j)) <= N)
            palindromes.push(number);
    }
 
    return palindromes;
}
 
// Function to find the minimum number of elements
// in a sorted array A[i..j] such that their sum is N
function minimumSubsetSize(A, N) {
    const n = A.length;
 
    // Initialize DP array
    const dp = new Array(n + 1);
    for (let i = 0; i <= n; i++) {
        dp[i] = new Array(N + 1).fill(0);
    }
 
    // Initialize base case
    for (let i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
 
    for (let j = 1; j <= N; j++) {
        dp[0][j] = Number.MAX_VALUE;
    }
 
    // Iterate over DP to get the current value from previous computation
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= N; j++) {
            if (A[i - 1] > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = Math.min(1 + dp[i - 1][j - A[i - 1]], dp[i - 1][j]);
            }
        }
    }
 
    // Return the final answer stored in DP
    return dp[n][N];
}
 
// Function to find the minimum number of palindromes
// that N can be expressed as a sum of
function minimumNoOfPalindromes(N) {
    // Getting the list of all palindromes up to N
    const palindromes = generatePalindromes(N);
 
    // Sorting the list of palindromes
    palindromes.sort((a, b) => a - b);
 
    // Returning the required value
    return minimumSubsetSize(palindromes, N);
}
 
// Driver Code
const N = 65;
console.log(minimumNoOfPalindromes(N));

Output

3

Time Complexity: O(N*M)
Auxiliary Space: O(N*M)


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Largest square that can be inscribed in a semicircle Largest square that can be inscribed in a semicircle
Find the sum of infinite series 1^2.x^0 + 2^2.x^1 + 3^2.x^2 + 4^2.x^3 +....... Find the sum of infinite series 1^2.x^0 + 2^2.x^1 + 3^2.x^2 + 4^2.x^3 +.......
Largest trapezoid that can be inscribed in a semicircle Largest trapezoid that can be inscribed in a semicircle
Minimum Players required to win the game Minimum Players required to win the game
Area of a largest square fit in a right angle triangle Area of a largest square fit in a right angle triangle

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 7



 

Horje