Encuentre un número tal que la suma de N con él sea un palíndromo

Dado un número muy grande N , [1 ≤ longitud del dígito de N (n) ≤ 10 ⁶ ], la tarea es encontrar algún número entero positivo de la misma longitud que N sin ceros a la izquierda, tal que la suma de estos dos números sea un palíndromo.

Ejemplos :

Entrada : N = 54321
Salida : 45678
Explicación : 54321 + 45678 = 99999 que es un palíndromo.

Entrada : N = 999
Salida : 112

Enfoque : para resolver el problema, siga la siguiente idea:

Si el número no empieza por 9 entonces haz el palíndromo de 9999…… de longitud de N y si el número empieza por 9 entonces haz el palíndromo de 1111….. de longitud de (n + 1).

• Entonces, el número resultante si no comienza con 9 es (9999….. to n – N). 
• Y, el número resultante si comienza con 9 es (11111….. a n+1 – N). 

Siga los pasos a continuación para resolver el problema:

• Encuentre el número de dígitos presentes en N.
• Si N comienza con 9:
  • Entonces considere que la suma es [ 1111…to (n+1) ].
  • Luego calcule el número como se mencionó anteriormente.
• Si N no comienza con 9:
  • Luego considere que la suma es [ 999…to n ].
  • Obtenga el número siguiendo el proceso mencionado anteriormente.

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement the above approach
 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
// Function to find difference
// of two large strings
string findDiff(string str1, string str2)
{
    // Take an empty string for storing result
    string str = "";
 
    // Calculate length of both string
    int n1 = str1.length(), n2 = str2.length();
 
    // Reverse both of strings
    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
 
    int carry = 0;
 
    // Run loop till small string length
    // and subtract digit of str1 to str2
    for (int i = 0; i < n2; i++) {
        int sub
            = ((str1[i] - '0') - (str2[i] - '0') - carry);
 
        // If subtraction is less then zero
        // then we 10 into sub and
        // take carry as 1 for calculating
        // next step
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
 
        str.push_back(sub + '0');
    }
 
    // Subtract remaining digits of
    // larger number
    for (int i = n2; i < n1; i++) {
        int sub = ((str1[i] - '0') - carry);
 
        // If the sub value is -ve,
        // then make it positive
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
    }
 
    // Reverse resultant string
    reverse(str.begin(), str.end());
    return str;
}
 
// Function to find the number which adds up
// to N makes the resultant number palindrome
string findPalin(string N)
{
    // Initialize variables
    ll n = N.size();
    string str = "";
 
    // If string starts with 9
    if (N[0] == '9') {
        while (n--) {
            str += '1';
        }
        str += '1';
        return findDiff(str, N);
    }
 
    // If string doesn't start with 9
    else {
        for (ll i = 0; i < n; i++) {
            str += ((9 - (N[i] - '0')) + '0');
        }
        return str;
    }
}
 
// Driver Code
int main()
{
    string N = "54321";
 
    // Function Call
    cout << findPalin(N);
    return 0;
}

<script>
 
// JavaScript code to implement the above approach
 
// Function to find difference
// of two large strings
function findDiff(str1, str2)
{
    // Take an empty string for storing result
    let str = "";
 
    // Calculate length of both string
    let n1 = str1.length, n2 = str2.length;
 
    // Reverse both of strings
    str1 = str1.split("").reverse().join("");
    str2 = str2.split("").reverse().join("");
 
    let carry = 0;
 
    // Run loop till small string length
    // and subtract digit of str1 to str2
    for (let i = 0; i < n2; i++) {
        let sub
            = ((str1[i] - '0') - (str2[i] - '0') - carry);
 
        // If subtraction is less then zero
        // then we 10 into sub and
        // take carry as 1 for calculating
        // next step
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
 
        str += sub.toString();
    }
 
    // Subtract remaining digits of
    // larger number
    for (let i = n2; i < n1; i++) {
        let sub = ((str1.charCodeAt(i) - '0'.charCodeAt(0)) - carry);
 
        // If the sub value is -ve,
        // then make it positive
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
    }
 
    // Reverse resultant string
    str = str.split().reverse().join("");
    return str;
}
 
// Function to find the number which adds up
// to N makes the resultant number palindrome
function findPalin(N)
{
    // Initialize variables
    let n = N.length;
    let str = "";
 
    // If string starts with 9
    if (N[0] == '9') {
        while (n--) {
            str += '1';
        }
        str += '1';
        return findDiff(str, N);
    }
 
    // If string doesn't start with 9
    else {
        for (let i = 0; i < n; i++) {
            str += (9 - parseInt(N[i])).toString();
        }
        return str;
    }
}
 
// Driver Code
let N = "54321";
 
// Function Call
document.write(findPalin(N),"</br>");
 
// This code is contributed by shinjanpatra
 
</script>

// Java code to implement the above approach
 
 
import java.util.*;
 
class GFG{
 
// Function to find difference
// of two large Strings
static String findDiff(String str1, String str2)
{
    // Take an empty String for storing result
    String str = "";
 
    // Calculate length of both String
    int n1 = str1.length(), n2 = str2.length();
 
    // Reverse both of Strings
    str1 = reverse(str1);
    str2 = reverse(str2);
 
    int carry = 0;
 
    // Run loop till small String length
    // and subtract digit of str1 to str2
    for (int i = 0; i < n2; i++) {
        int sub
            = ((str1.charAt(i) - '0') - (str2.charAt(i) - '0') - carry);
 
        // If subtraction is less then zero
        // then we 10 into sub and
        // take carry as 1 for calculating
        // next step
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
 
        str+=(sub + '0');
    }
 
    // Subtract remaining digits of
    // larger number
    for (int i = n2; i < n1; i++) {
        int sub = ((str1.charAt(i) - '0') - carry);
 
        // If the sub value is -ve,
        // then make it positive
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
    }
 
    // Reverse resultant String
    str = reverse(str);
    return str;
}
 
// Function to find the number which adds up
// to N makes the resultant number palindrome
static String findPalin(String N)
{
    // Initialize variables
    long n = N.length();
    String str = "";
 
    // If String starts with 9
    if (N.charAt(0) == '9') {
        while (n-- >0) {
            str += '1';
        }
        str += '1';
        return findDiff(str, N);
    }
 
    // If String doesn't start with 9
    else {
        for (int i = 0; i < n; i++) {
            str += String.valueOf(9 - Integer.parseInt(String.valueOf(N.charAt(i))));
        }
        return str;
    }
}
static String reverse(String input) {
    char[] a = input.toCharArray();
    int l, r = a.length - 1;
    for (l = 0; l < r; l++, r--) {
        char temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }
    return String.valueOf(a);
}
// Driver Code
public static void main(String[] args)
{
    String N = "54321";
 
    // Function Call
    System.out.print(findPalin(N));
}
}
 
// This code contributed by shikhasingrajput

45678

Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)