Número de palíndromo más cercano (la diferencia absoluta es min)

Posted on by Rudeus Greyrat

Dado un número N, nuestra tarea es encontrar el número palíndromo más cercano cuya diferencia absoluta con el número dado sea mínima y la diferencia absoluta debe ser mayor que 0. 

Ejemplos: 

Input :  N = 121 
Output : 131 or 111   
Both having equal absolute difference
with the given number.

Input : N = 1234
Output : 1221

Preguntado en: Amazon 

La solución simple es encontrar el número palíndromo más grande que es más pequeño que el número dado y también encontrar el primer número palíndromo que es mayor que el número dado. números.

A continuación se muestra la implementación de la idea anterior:

C++

// C++ Program to find the closest Palindrome
// number
#include <bits/stdc++.h>
using namespace std;
 
// function check Palindrome
bool isPalindrome(string n)
{
    for (int i = 0; i < n.size() / 2; i++)
        if (n[i] != n[n.size() - 1 - i])
            return false;
    return true;
}
 
// convert number into String
string convertNumIntoString(int num)
{
 
    // base case:
    if (num == 0)
        return "0";
 
    string Snum = "";
    while (num > 0) {
        Snum += (num % 10 - '0');
        num /= 10;
    }
    return Snum;
}
 
// function return closest Palindrome number
int closestPalindrome(int num)
{
 
    // case1 : largest palindrome number
    // which is smaller to given number
    int RPNum = num - 1;
 
    while (!isPalindrome(convertNumIntoString(abs(RPNum))))
        RPNum--;
 
    // Case 2 : smallest palindrome number
    // which is greater than given number
    int SPNum = num + 1;
 
    while (!isPalindrome(convertNumIntoString(SPNum)))
        SPNum++;
 
    // check absolute difference
    if (abs(num - RPNum) > abs(num - SPNum))
        return SPNum;
    else
        return RPNum;
}
 
// Driver program to test above function
int main()
{
    int num = 121;
    cout << closestPalindrome(num) << endl;
    return 0;
}

Java

// Java program to find the closest
// Palindrome number
import java.io.*;
 
class GFG{
 
// Function to check Palindrome   
public static boolean isPalindrome(String s)
{
    int left = 0;
    int right = s.length() - 1;
 
    while (left < right)
    {
        if (s.charAt(left) !=
            s.charAt(right))
        {
            return false;
        }
        left++;
        right--;
    }
    return true;
}
 
// Function return closest Palindrome number
public static void closestPalindrome(int num)
{
     
    // Case1 : largest palindrome number
    // which is smaller to given number
    int RPNum = num - 1;
     
    while (isPalindrome(Integer.toString(RPNum)) == false)
    {
        RPNum--;
    }
     
    // Case 2 : smallest palindrome number
    // which is greater than given number
    int SPNum = num + 1;
     
    while (isPalindrome(Integer.toString(SPNum)) == false)
    {
        SPNum++;
    }
 
    // Check absolute difference
    if (Math.abs(num - SPNum) <
        Math.abs(num - RPNum))
    {
        System.out.println(SPNum);
    }
    else
        System.out.println(RPNum);
}
 
// Driver code    
public static void main(String[] args)
{
    int n = 121;
     
    closestPalindrome(n);
}
}
 
// This code is contributed by kes333hav

Python3

# Python3 program to find the
# closest Palindrome number
 
# Function to check Palindrome
 
 
def isPalindrome(n):
 
    for i in range(len(n) // 2):
        if (n[i] != n[-1 - i]):
            return False
 
    return True
 
# Convert number into String
 
 
def convertNumIntoString(num):
 
    Snum = str(num)
    return Snum
 
# Function return closest Palindrome number
 
 
def closestPalindrome(num):
 
    # Case1 : largest palindrome number
    # which is smaller than given number
    RPNum = num - 1
    while (not isPalindrome(
           convertNumIntoString(abs(RPNum)))):
        RPNum -= 1
 
    # Case2 : smallest palindrome number
    # which is greater than given number
    SPNum = num + 1
    while (not isPalindrome(
           convertNumIntoString(SPNum))):
        SPNum += 1
 
    # Check absolute difference
    if (abs(num - RPNum) > abs(num - SPNum)):
        return SPNum
    else:
        return RPNum
 
 
# Driver Code
if __name__ == '__main__':
 
    num = 121
 
    print(closestPalindrome(num))
 
# This code is contributed by himanshu77

C#

// C# program to find the closest
// Palindrome number
using System;
 
class GFG{
 
// Function to check Palindrome
public static bool isPalindrome(string s)
{
    int left = 0;
    int right = s.Length - 1;
 
    while (left < right)
    {
        if (s[left] != s[right])
        {
            return false;
        }
        left++;
        right--;
    }
    return true;
}
 
// Function return closest Palindrome number
public static void closestPalindrome(int num)
{
     
    // Case1 : largest palindrome number
    // which is smaller to given number
    int RPNum = num - 1;
 
    while (isPalindrome(RPNum.ToString()) == false)
    {
        RPNum--;
    }
 
    // Case 2 : smallest palindrome number
    // which is greater than given number
    int SPNum = num + 1;
 
    while (isPalindrome(SPNum.ToString()) == false)
    {
        SPNum++;
    }
 
    // Check absolute difference
    if (Math.Abs(num - SPNum) <
        Math.Abs(num - RPNum))
    {
        Console.WriteLine(SPNum);
    }
    else
        Console.WriteLine(RPNum);
}
 
// Driver code
public static void Main(string[] args)
{
    int n = 121;
 
    closestPalindrome(n);
}
}
 
// This code is contributed by ukasp

PHP

<?php
// PHP Program to find the
// closest Palindrome number
 
// function check Palindrome
function isPalindrome($n)
{
 for ($i = 0; $i < floor(strlen($n) /  2); $i++)
    if ($n[$i] != $n[strlen($n) - 1 - $i])
    return false;
return true;
}
 
// convert number into String
function convertNumIntoString($num)
{
 
// base case:
if ($num == 0)
    return "0";
$Snum = "";
while ($num > 0)
{
    $Snum .= ($num % 10 - '0');
    $num =(int)($num / 10);
}
return $Snum;
}
 
// function return closest
// Palindrome number
function closestPalindrome($num)
{
 
// case1 : largest palindrome number
// which is smaller to given number
$RPNum = $num - 1;
 
while (!isPalindrome(convertNumIntoString(abs($RPNum))))
    $RPNum--;
 
// Case 2 : smallest palindrome number
// which is greater than given number
$SPNum = $num + 1;
 
while (!isPalindrome(convertNumIntoString($SPNum)))
    $SPNum++;
 
// check absolute difference
if (abs($num - $RPNum) > abs($num - $SPNum))
    return $SPNum;
else
    return $RPNum;
}
 
    // Driver code
    $num = 121;
    echo closestPalindrome($num)."\n";
 
// This code is contributed by mits
?>

Javascript

<script>
 
// JavaScript Program to find the closest Palindrome
// number
 
// function check Palindrome
function isPalindrome(n)
{
    for (let i = 0; i < Math.floor(n.length / 2); i++)
        if (n[i] != n[n.length - 1 - i])
            return false;
    return true;
}
 
// convert number into String
function convertNumIntoString(num)
{
 
    // base case:
    if (num == 0)
        return "0";
 
    let Snum = num + '';
    return Snum;
}
 
// function return closest Palindrome number
function closestPalindrome(num)
{
 
    // case1 : largest palindrome number
    // which is smaller to given number
    let RPNum = num - 1;
 
    while (!isPalindrome(convertNumIntoString(Math.abs(RPNum))))
        RPNum--;
 
    // Case 2 : smallest palindrome number
    // which is greater than given number
    let SPNum = num + 1;
 
    while (!isPalindrome(convertNumIntoString(SPNum)))
        SPNum++;
 
    // check absolute difference
    if (Math.abs(num - RPNum) > Math.abs(num - SPNum))
        return SPNum;
    else
        return RPNum;
}
 
// Driver program to test above function
let num = 121;
document.write(closestPalindrome(num),"</br>");
     
// This code is contributed by shinjanpatra.
</script>

Producción: 

111

Una solución eficiente es considerar los siguientes casos. 
Caso 1: si un número contiene todos los 9, obtenemos el siguiente palíndromo más cercano simplemente agregando 2 en él. num = 999: salida: num + 2 = 1001.
Caso 2:  
Caso 2 a: una forma posible de acercarse al palindrómico más cercano copiando la primera mitad y agregando una imagen especular al final si es así. Mitad izquierda: Por ejemplo, el lado izquierdo de “ 123 456” es “123” y la mitad izquierda de “ 12345” es “1 2”. Para convertir a palíndromo, podemos tomar el espejo de su mitad izquierda o tomar el espejo de su mitad derecha. Sin embargo, si tomamos el espejo de la mitad derecha, no se garantiza que el palíndromo así formado sea el palíndromo más cercano. Entonces, debemos tomar el espejo del lado izquierdo y copiarlo en el lado derecho. 

Let's number : 123456 
After copy and append reverse of it at the end number looks like:
we get palindrome 123321

caso 2b y 2c: dos formas más posibles de obtener el número palindrómico más cercano al disminuir e incrementar el dígito medio en uno en el palíndromo. 

A continuación se muestra la implementación de la idea anterior:  

C++

// C++ program to find the closest Palindrome number
#include <bits/stdc++.h>
using namespace std;
 
#define CToI(x) (x - '0')
#define IToC(x) (x + '0')
 
// function check Palindrome
bool isPalindrome(string n)
{
    for (int i = 0; i < n.size() / 2; i++)
        if (n[i] != n[n.size() - 1 - i])
            return false;
    return true;
}
 
// check all 9's
bool checkAll9(string num)
{
    for (int i = 0; i < num.size(); i++)
        if (num[i] != '9')
            return false;
    return true;
}
 
// Add carry to the number of given size
string carryOperation(string num, int carry, int size)
{
    if (carry == -1)
    {
        int i = size - 1;
        while (i >= 0 && num[i] == '0')
            num[i--] = '9';
        if (i >= 0)
            num[i] = IToC(CToI(num[i]) - 1);
    }
    else
    {
        for (int i = size - 1; i >= 0; i--)
        {
            int digit = CToI(num[i]);
            num[i] = IToC((digit + carry) % 10);
            carry = (digit + carry) / 10;
        }
    }
    return num;
}
 
// function return the closest number
// to given number
string MIN(long long int num,
           long long int num1,
           long long int num2,
           long long int num3)
{
 
    long long int Diff1 = abs(num - num1);
    long long int Diff2 = abs(num - num2);
    long long int Diff3 = abs(num3 - num);
 
    if (Diff1 < Diff2 && Diff1 < Diff3 &&
        num1 != num)
        return to_string(num1);
    else if (Diff3 < Diff2 && (Diff1 == 0 ||
             Diff3 < Diff1))
        return to_string(num3);
    else
        return to_string(num2);
}
 
// function return closest Palindrome number
string closestPlandrome(string num)
{
 
    // base case
    if (num.size() == 1)
        return (to_string(stoi(num) - 1));
 
    // case 2:
    // If a number contains all 9's
    if (checkAll9(num))
    {
        string str = "1";
        return str.append(num.size() - 1, '0') + "1";
    }
 
    int size_ = num.size();
 
    // case 1 a:
    // copy first half and reverse it and append it
    // at the end of first half
    string FH = num.substr(0, size_ / 2);
    string odd;
 
    // odd length
    if (size_ % 2 != 0)
        odd = num[size_ / 2];
 
    // reverse
    string SH = FH;
    reverse(SH.begin(), SH.end());
 
    // store three nearest Palindrome numbers
    string RPNUM = "", EPNUM = "", LPNUM = "";
    string tempFH = "";
    string tempSH = "";
 
    if (size_ % 2 != 0)
    {
        EPNUM = FH + odd + SH;
        if (odd == "0")
        {
            tempFH = carryOperation(FH, -1, FH.size());
            tempSH = tempFH;
            reverse(tempSH.begin(), tempSH.end());
            RPNUM = tempFH + "9" + tempSH;
        }
        else
            RPNUM = FH + to_string(stoi(odd) - 1) + SH;
 
        // To handle carry
        if (odd == "9")
        {
            tempFH = carryOperation(FH, 1, FH.size());
            tempSH = tempFH;
            reverse(tempSH.begin(), tempSH.end());
            LPNUM = tempFH + "0" + tempSH;
        }
        else
            LPNUM = FH + to_string(stoi(odd) + 1) + SH;
    }
 
    // for even case
    else
    {
        int n = FH.size();
        tempFH = FH;
        EPNUM = FH + SH;
        if (FH[n - 1] == '0')
            tempFH = carryOperation(FH, -1, n);
        else
            tempFH[n - 1] = IToC(CToI(FH[n - 1]) - 1);
 
        tempSH = tempFH;
        reverse(tempSH.begin(), tempSH.end());
        RPNUM = tempFH + tempSH;
 
        tempFH = FH;
        if (FH[n - 1] == '9')
            tempFH = carryOperation(FH, 1, n);
        else
            tempFH[n - 1] = IToC(CToI(tempFH[n - 1]) + 1);
 
        tempSH = tempFH;
        reverse(tempSH.begin(), tempSH.end());
        LPNUM = tempFH + tempSH;
    }
 
    // return the closest palindrome numbers
    return MIN(stoll(num), stoll(EPNUM), stoll(RPNUM),
                                         stoll(LPNUM));
}
 
// Driver program to test above function
int main()
{
    string num = "123456";
    cout << closestPlandrome(num) << endl;
    return 0;
}

Producción: 

123321

Complejidad del tiempo: O(d) (d es el número de dígitos en un número dado)
 

Publicación traducida automáticamente

Artículo escrito por Nishant_Singh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *