Número mínimo de palíndromos necesarios para expresar N como suma | conjunto 2

Dado un número N, tenemos que encontrar el número mínimo de palíndromos necesarios para expresar N como suma de ellos. 
Ejemplos : 

Entrada : N = 11 
Salida : 1 
Explicación : 11 es en sí mismo un palíndromo.
Entrada : N = 65 
Salida : 3 
Explicación : 65 se puede expresar como la suma de tres palíndromos (55, 9, 1).

En la publicación anterior , discutimos un enfoque de programación dinámica para este problema que tenía una complejidad de tiempo y espacio de O (N ^3/2 ).
Cilleruelo, Luca y Baxter demostraron en un trabajo de investigación de 2016 que todo número se puede expresar como la suma de un máximo de tres palíndromos en cualquier base b >= 5 (este límite inferior se mejoró posteriormente a 3). Para la demostración de este teorema, consulte el artículo original . Podemos hacer uso de este teorema asumiendo con seguridad que la respuesta es tres si el número N no es en sí mismo un palíndromo y no puede expresarse como la suma de dos palíndromos.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to find the minimum number of
// palindromes required to express N as a sum
 
#include <bits/stdc++.h>
using namespace std;
 
// 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 palindromes required
// to express N as a sum
int minimumNoOfPalindromes(int N)
{
    // Checking if the number is a palindrome
    string a, b = a = to_string(N);
    reverse(b.begin(), b.end());
    if (a == b)
        return 1;
 
    // Checking if the number is a
    // sum of two palindromes
 
    // Getting the list of all palindromes upto N
    vector<int> palindromes = generatePalindromes(N);
 
    // Sorting the list of palindromes
    sort(palindromes.begin(), palindromes.end());
 
    int l = 0, r = palindromes.size() - 1;
    while (l < r) {
        if (palindromes[l] + palindromes[r] == N)
            return 2;
        else if (palindromes[l] + palindromes[r] < N)
            ++l;
        else
            --r;
    }
 
    // The answer is three if the
    // control reaches till this point
    return 3;
}
 
// Driver code
int main()
{
    int N = 65;
     
    cout << minimumNoOfPalindromes(N);
     
    return 0;
}

// Java program to find the minimum number of
// palindromes required to express N as a sum
import java.util.*;
 
class GFG
{
 
    // 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 % 2 == 1)
        {
            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 Vector<Integer> generatePalindromes(int N)
    {
        Vector<Integer> palindromes = new Vector<>();
        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;
    }
 
    static String reverse(String input)
    {
        char[] temparray = input.toCharArray();
        int left, right = 0;
        right = temparray.length - 1;
 
        for (left = 0; left < right; left++, right--)
        {
            // Swap values of left and right
            char temp = temparray[left];
            temparray[left] = temparray[right];
            temparray[right] = temp;
        }
        return String.valueOf(temparray);
    }
 
    // Function to find the minimum
    // number of palindromes required
    // to express N as a sum
    static int minimumNoOfPalindromes(int N)
    {
        // Checking if the number is a palindrome
        String a = String.valueOf(N);
        String b = String.valueOf(N);
        b = reverse(b);
        if (a.equals(b))
        {
            return 1;
        }
 
        // Checking if the number is a
        // sum of two palindromes
        // Getting the list of all palindromes upto N
        Vector<Integer> palindromes = generatePalindromes(N);
 
        // Sorting the list of palindromes
        Collections.sort(palindromes);
 
        int l = 0, r = palindromes.size() - 1;
        while (l < r)
        {
            if (palindromes.get(l) + palindromes.get(r) == N)
            {
                return 2;
            }
            else if (palindromes.get(l) + palindromes.get(r) < N)
            {
                ++l;
            }
            else
            {
                --r;
            }
        }
 
    // The answer is three if the
        // control reaches till this point
        return 3;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 65;
        System.out.println(minimumNoOfPalindromes(N));
    }
}
 
// This code is contributed by Rajput-Ji

# Python3 program to find the minimum number of
# palindromes required to express N as a sum
 
# A utility for creating palindrome
def createPalindrome(_input, isOdd):
  
    n = 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 = []
 
    # Run two times for odd and even
    # length palindromes
    for j in range(0, 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:
            palindromes.append(number)
            i += 1
            number = createPalindrome(i, j)
      
    return palindromes
  
# Function to find the minimum
# number of palindromes required
# to express N as a sum
def minimumNoOfPalindromes(N):
  
    # Checking if the number is a palindrome
    b = a = str(N)
    b = b[::-1]
    if a == b:
        return 1
 
    # Checking if the number is a
    # sum of two palindromes
 
    # Getting the list of all palindromes upto N
    palindromes = generatePalindromes(N)
 
    # Sorting the list of palindromes
    palindromes.sort()
 
    l, r = 0, len(palindromes) - 1
    while l < r:
         
        if palindromes[l] + palindromes[r] == N:
            return 2
        elif palindromes[l] + palindromes[r] < N:
            l += 1
        else:
            r -= 1
      
    # The answer is three if the
    # control reaches till this point
    return 3
  
# Driver code
if __name__ == "__main__":
  
    N = 65
    print(minimumNoOfPalindromes(N))
     
# This code is contributed by Rituraj Jain

// C# program to find the
// minimum number of palindromes
// required to express N as a sum
using System;
using System.Collections.Generic;
class GFG{
 
// 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 % 2 == 1)
  {
    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;
}
 
static String reverse(String input)
{
  char[] temparray = input.ToCharArray();
  int left, right = 0;
  right = temparray.Length - 1;
 
  for (left = 0;
       left < right; left++, right--)
  {
    // Swap values of left and right
    char temp = temparray[left];
    temparray[left] = temparray[right];
    temparray[right] = temp;
  }
   
  return String.Join("", temparray);
}
 
// Function to find the minimum
// number of palindromes required
// to express N as a sum
static int minimumNoOfPalindromes(int N)
{
  // Checking if the number
  // is a palindrome
  String a = String.Join("", N);
  String b = String.Join("", N);
  b = reverse(b);
   
  if (a.Equals(b))
  {
    return 1;
  }
 
  // Checking if the number is
  // a sum of two palindromes
  // Getting the list of all
  // palindromes upto N
  List<int> palindromes =
            generatePalindromes(N);
 
  // Sorting the list
  // of palindromes
  palindromes.Sort();
 
  int l = 0,
      r = palindromes.Count - 1;
   
  while (l < r)
  {
    if (palindromes[l] +
        palindromes[r] == N)
    {
      return 2;
    }
    else if (palindromes[l] +
             palindromes[r] < N)
    {
      ++l;
    }
    else
    {
      --r;
    }
  }
 
  // The answer is three if the
  // control reaches till this point
  return 3;
}
 
// Driver code
public static void Main(String[] args)
{
  int N = 65;
  Console.WriteLine(minimumNoOfPalindromes(N));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript program to find the
// minimum number of palindromes
// required to express N as a sum
 
// A utility for creating palindrome
function createPalindrome(input, isOdd)
{
  var n = input;
  var 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 % 2 == 1)
  {
    n = parseInt(n/10);
  }
 
  // Creates palindrome by
  // just appending reverse
  // of number to itself
  while (n > 0)
  {
    palin = palin * 10 + (n % 10);
    n = parseInt(n/10);
  }
 
  return palin;
}
 
// Function to generate palindromes
function generatePalindromes(N)
{
  var palindromes = [];
  var number;
 
  // Run two times for
  // odd and even length
  // palindromes
  for (var 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.
    var i = 1;
    while ((number = createPalindrome(i++,
                                      j)) <= N)
    {
      palindromes.push(number);
    }
  }
 
  return palindromes;
}
 
function reverse(input)
{
  var temparray = input.split('');
  var left, right = 0;
  right = temparray.length - 1;
 
  for (left = 0;
       left < right; left++, right--)
  {
    // Swap values of left and right
    var temp = temparray[left];
    temparray[left] = temparray[right];
    temparray[right] = temp;
  }
   
  return temparray.join('');
}
 
// Function to find the minimum
// number of palindromes required
// to express N as a sum
function minimumNoOfPalindromes(N)
{
  // Checking if the number
  // is a palindrome
  var a = N.toString();
  var b = N.toString();
  b = reverse(b);
   
  if (a == b)
  {
    return 1;
  }
 
  // Checking if the number is
  // a sum of two palindromes
  // Getting the list of all
  // palindromes upto N
  var palindromes =
            generatePalindromes(N);
 
  // Sorting the list
  // of palindromes
  palindromes.sort();
 
  var l = 0,
      r = palindromes.length - 1;
   
  while (l < r)
  {
    if (palindromes[l] +
        palindromes[r] == N)
    {
      return 2;
    }
    else if (palindromes[l] +
             palindromes[r] < N)
    {
      ++l;
    }
    else
    {
      --r;
    }
  }
 
  // The answer is three if the
  // control reaches till this point
  return 3;
}
 
// Driver code
var N = 65;
document.write(minimumNoOfPalindromes(N));
 
// This code is contributed by rrrtnx.
</script>

3

Complejidad del tiempo : O(√(N)log N).