Dado un número, encuentra el siguiente palíndromo más pequeño mayor que este número. Por ejemplo, si el número de entrada es «2 3 5 4 5», la salida debería ser «2 3 6 3 2». Y si el número de entrada es «9 9 9», la salida debe ser «1 0 0 1».
Se supone que la entrada es una array. Cada entrada en la array representa un dígito en el número de entrada. Deje que la array sea ‘num[]’ y el tamaño de la array sea ‘n’
Puede haber tres tipos diferentes de entradas que deben manejarse por separado.
1) El número de entrada es palíndromo y tiene solo 9. Por ejemplo, “9 9 9”. La salida debe ser “1 0 0 1”
2) El número de entrada no es un palíndromo. Por ejemplo “1 2 3 4”. La salida debe ser “1 3 3 1”
3) El número de entrada es palíndromo y no tiene todos los 9. Por ejemplo, “1 2 2 1”. La salida debe ser «1 3 3 1».
La solución para el tipo de entrada 1 es fácil. La salida contiene n + 1 dígitos donde los dígitos de las esquinas son 1, y todos los dígitos entre los dígitos de las esquinas son 0.
Ahora, primero hablemos sobre los tipos de entrada 2 y 3. ¿Cómo convertir un número dado en un palíndromo mayor? Para entender la solución, primero definamos los siguientes dos términos:
Lado izquierdo: La mitad izquierda del número dado. El lado izquierdo de «1 2 3 4 5 6» es «1 2 3» y el lado izquierdo de «1 2 3 4 5» es «1 2»
Lado derecho: La mitad derecha del número dado. El lado derecho de «1 2 3 4 5 6» es «4 5 6» y el lado derecho de «1 2 3 4 5» es «4 5»
Para convertir a palíndromo, podemos tomar el espejo de su lado izquierdo o tomar el espejo de su lado derecho. Sin embargo, si tomamos el espejo del lado derecho, entonces no se garantiza que el palíndromo así formado sea el siguiente palíndromo más grande. Entonces, debemos tomar el espejo del lado izquierdo y copiarlo en el lado derecho. Pero hay algunos casos que deben manejarse de diferentes maneras. Consulte los siguientes pasos.
Comenzaremos con dos índices i y j. i apuntando a los dos elementos del medio (o apuntando a dos elementos alrededor del elemento del medio en caso de que n sea impar). Uno por uno alejamos i y j uno del otro.
Paso 1. Inicialmente, ignore la parte del lado izquierdo que es igual a la parte correspondiente del lado derecho. Por ejemplo, si el número es «8 3 4 2 2 4 6 9″, ignoramos los cuatro elementos del medio. i ahora apunta al elemento 3 y j ahora apunta al elemento 6.
Paso 2. Después del paso 1, surgen los siguientes casos:
Caso 1: Los índices i y j cruzan el límite.
Este caso se da cuando el número de entrada es palíndromo. En este caso, simplemente agregamos 1 al dígito del medio (o dígitos en caso de que n sea par), propagamos el acarreo hacia el dígito MSB del lado izquierdo y simultáneamente copiamos el espejo del lado izquierdo al lado derecho.
Por ejemplo, si el número dado es “1 2 9 2 1”, incrementamos de 9 a 10 y propagamos el acarreo. Entonces el número se convierte en «1 3 0 3 1»
Caso 2: quedan dígitos entre el lado izquierdo y el lado derecho que no son iguales. Entonces, simplemente reflejamos el lado izquierdo hacia el lado derecho e intentamos minimizar el número formado para garantizar el siguiente palíndromo más pequeño.
En este caso, puede haber dos subcasos .
2.1) Copiar el lado izquierdo al lado derecho es suficiente, no necesitamos incrementar ningún dígito y el resultado es solo un espejo del lado izquierdo. A continuación se presentan algunos ejemplos de este subcaso.
El siguiente palíndromo para “7 8 3 3 2 2″ es “7 8 3 3 8 7”
El siguiente palíndromo para “1 2 5 3 2 2″ es “1 2 5 5 2 1”
El siguiente palíndromo para “1 4 5 8 7 6 7 8 3 2 2″ es “1 4 5 8 7 6 7 8 5 4 1”
¿Cómo verificamos este subcaso? Todo lo que necesitamos verificar es el dígito justo después de la parte ignorada en el paso 1. Este dígito está resaltado en los ejemplos anteriores. Si este dígito es mayor que el dígito correspondiente en el dígito del lado derecho, entonces copiar el lado izquierdo al lado derecho es suficiente y no necesitamos hacer nada más.
2.2) Copiar el lado izquierdo al lado derecho NO es suficiente. Esto sucede cuando el dígito definido arriba del lado izquierdo es más pequeño. A continuación se presentan algunos ejemplos de este caso.
El siguiente palíndromo para “7 1 3 3 2 2″ es “7 1 4 4 1 7”
El siguiente palíndromo para “1 2 3 4 6 2 8″ es “1 2 3 5 3 2 1”
El siguiente palíndromo para “9 4 1 8 7 9 7 8 3 2 2″ es “9 4 1 8 8 0 8 8 1 4 9”
Manejamos este subcaso como el Caso 1. Simplemente agregamos 1 al dígito del medio (o dígitos en caso de que n sea par) propagamos el acarreo hacia el dígito MSB del lado izquierdo y simultáneamente copiar el espejo del lado izquierdo al lado derecho.
Enfoque 1: Enfoque básico para encontrar el siguiente número palíndromo más pequeño.
C++
#include <bits/stdc++.h>
using namespace std;
// Function to check whether number is palindrome or not
int isPalindrome(int num)
{
// Declaring variables
int n, k, rev = 0;
// storing num in n so that we can compare it later
n = num;
// while num is not 0 we find its reverse and store in
// rev
while (num != 0) {
k = num % 10;
rev = (rev * 10) + k;
num = num / 10;
}
// check if num and its reverse are same
if (n == rev) {
return 1;
}
else {
return 0;
}
}
int main()
{
// Take any number to find its next palindrome number
int num = 9687;
// If number is not Palindrome we go to the next number
// using while loop
while (!isPalindrome(num)) {
num = num + 1;
}
// now we get the next Palindrome so let's print it
cout << "Next Palindrome :";
cout << num;
return 0;
}
// Contribute by :- Tejas Bhavsar
Java
import java.io.*;
class GFG
{
// Function to check whether number is palindrome or not
static int isPalindrome(int num)
{
// Declaring variables
int n, k, rev = 0;
// storing num in n so that we can compare it later
n = num;
// while num is not 0 we find its reverse and store
// in rev
while (num != 0) {
k = num % 10;
rev = (rev * 10) + k;
num = num / 10;
}
// check if num and its reverse are same
if (n == rev) {
return 1;
}
else {
return 0;
}
}
// Driver code
public static void main(String[] args)
{
// Take any number to find its next palindrome
// number
int num = 9687;
// If number is not Palindrome we go to the next
// number using while loop
while (isPalindrome(num) == 0) {
num = num + 1;
}
// now we get the next Palindrome so let's print it
System.out.print("Next Palindrome :");
System.out.print(num);
}
}
// This code is contributed by subhammahato348.
Python3
# Program to print find next palindrome
# number greater than given number.
# function to check a number is
# palindrome or not
def isPalindrome(num):
# Declaring variables
# storing num in n so that we can compare it later
n = num
rev = 0
# while num is not 0 we find its reverse and store
# in rev
while (num > 0):
k = num % 10
rev = (rev * 10) + k
num = num // 10
# check if num and its reverse are same
if (n == rev):
return True
else:
return False
# input number
num = 9687
# start check from next num;
num = num + 1
# Loop checks all numbers from given no.
# (num + 1) to next palindrome no.
while (True):
if (isPalindrome(num)):
break
num = num + 1
# printing the next palindrome
print("Next Palindrome :")
print(num)
# This code is contributed by sidharthsingh7898.
C#
using System;
class GFG {
// Function to check whether number is palindrome or not
static int isPalindrome(int num)
{
// Declaring variables
int n, k, rev = 0;
// storing num in n so that we can compare it later
n = num;
// while num is not 0 we find its reverse and store
// in rev
while (num != 0) {
k = num % 10;
rev = (rev * 10) + k;
num = num / 10;
}
// check if num and its reverse are same
if (n == rev) {
return 1;
}
else {
return 0;
}
}
// Driver code
public static void Main()
{
// Take any number to find its next palindrome
// number
int num = 9687;
// If number is not Palindrome we go to the next
// number using while loop
while (isPalindrome(num) == 0) {
num = num + 1;
}
// now we get the next Palindrome so let's print it
Console.Write("Next Palindrome :");
Console.Write(num);
}
}
// This code is contributed by subhammahato348.
Javascript
<script>
// Javascript program for the above approach
// Function to check whether number is palindrome or not
function isPalindrome(num)
{
// Declaring variables
let n, k, rev = 0;
// storing num in n so that we can compare it later
n = num;
// while num is not 0 we find its reverse and store
// in rev
while (num != 0) {
k = num % 10;
rev = (rev * 10) + k;
num = Math.floor(num / 10);
}
// check if num and its reverse are same
if (n == rev) {
return 1;
}
else {
return 0;
}
}
// Driver Code
// Take any number to find its next palindrome
// number
let num = 9687;
// If number is not Palindrome we go to the next
// number using while loop
while (isPalindrome(num) == 0) {
num = num + 1;
}
// now we get the next Palindrome so let's print it
document.write("Next Palindrome :");
document.write(num);
// This code is contributed by splevel62.
</script>
Producción
Next Palindrome :9779
Complejidad de Tiempo: O(num * |num|)
Complejidad espacial: O(1)
C++
#include <iostream>
using namespace std;
// Utility that prints out an array on a line
void printArray(int arr[], int n)
{
int i;
for(i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
// A utility function to check if num has all 9s
int AreAll9s(int* num, int n )
{
int i;
for(i = 0; i < n; ++i)
if (num[i] != 9)
return 0;
return 1;
}
// Returns next palindrome of a given number num[].
// This function is for input type 2 and 3
void generateNextPalindromeUtil (int num[], int n )
{
// 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 leftsmaller = false;
// End of left side is always 'mid -1'
int i = mid - 1;
// Beginning of right side depends
// if n is odd or even
int j = (n % 2) ? mid + 1 : mid;
// Initially, ignore the middle same digits
while (i >= 0 && num[i] == num[j])
i--, j++;
// Find if the middle digit(s) need to be
// incremented or not (or copying left
// side is not sufficient)
if (i < 0 || num[i] < num[j])
leftsmaller = true;
// Copy the mirror of left to tight
while (i >= 0)
{
num[j] = num[i];
j++;
i--;
}
// Handle the case where middle digit(s) must
// be incremented. This part of code is for
// CASE 1 and CASE 2.2
if (leftsmaller == true)
{
int carry = 1;
i = mid - 1;
// If there are odd digits, then increment
// the middle digit and store the carry
if (n % 2 == 1)
{
num[mid] += carry;
carry = num[mid] / 10;
num[mid] %= 10;
j = mid + 1;
}
else
j = mid;
// Add 1 to the rightmost digit of the
// left side, propagate the carry towards
// MSB digit and simultaneously copying
// mirror of the left side to the right side.
while (i >= 0)
{
num[i] += carry;
carry = num[i] / 10;
num[i] %= 10;
// Copy mirror to right
num[j++] = num[i--];
}
}
}
// The function that prints next palindrome
// of a given number num[] with n digits.
void generateNextPalindrome(int num[], int n)
{
int i;
printf("Next palindrome is:");
// Input type 1: All the digits are 9, simply o/p 1
// followed by n-1 0's followed by 1.
if (AreAll9s(num, n))
{
printf("1 ");
for(i = 1; i < n; i++)
printf("0 ");
printf("1");
}
// Input type 2 and 3
else
{
generateNextPalindromeUtil(num, n);
// print the result
printArray (num, n);
}
}
// Driver code
int main()
{
int num[] = { 9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2 };
int n = sizeof(num) / sizeof(num[0]);
generateNextPalindrome(num, n);
return 0;
}
// This code is contributed by rohan07
C
#include <stdio.h>
// A utility function to print an array
void printArray (int arr[], int n);
// A utility function to check if num has all 9s
int AreAll9s (int num[], int n );
// Returns next palindrome of a given number num[].
// This function is for input type 2 and 3
void generateNextPalindromeUtil (int num[], int n )
{
// 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 leftsmaller = false;
// end of left side is always 'mid -1'
int i = mid - 1;
// Beginning of right side depends if n is odd or even
int j = (n % 2)? mid + 1 : mid;
// Initially, ignore the middle same digits
while (i >= 0 && num[i] == num[j])
i--,j++;
// Find if the middle digit(s) need to be incremented or not (or copying left
// side is not sufficient)
if ( i < 0 || num[i] < num[j])
leftsmaller = true;
// Copy the mirror of left to tight
while (i >= 0)
{
num[j] = num[i];
j++;
i--;
}
// Handle the case where middle digit(s) must be incremented.
// This part of code is for CASE 1 and CASE 2.2
if (leftsmaller == true)
{
int carry = 1;
i = mid - 1;
// If there are odd digits, then increment
// the middle digit and store the carry
if (n%2 == 1)
{
num[mid] += carry;
carry = num[mid] / 10;
num[mid] %= 10;
j = mid + 1;
}
else
j = mid;
// Add 1 to the rightmost digit of the left side, propagate the carry
// towards MSB digit and simultaneously copying mirror of the left side
// to the right side.
while (i >= 0)
{
num[i] += carry;
carry = num[i] / 10;
num[i] %= 10;
num[j++] = num[i--]; // copy mirror to right
}
}
}
// The function that prints next palindrome of a given number num[]
// with n digits.
void generateNextPalindrome( int num[], int n )
{
int i;
printf("Next palindrome is:");
// Input type 1: All the digits are 9, simply o/p 1
// followed by n-1 0's followed by 1.
if( AreAll9s( num, n ) )
{
printf( "1 ");
for( i = 1; i < n; i++ )
printf( "0 " );
printf( "1" );
}
// Input type 2 and 3
else
{
generateNextPalindromeUtil ( num, n );
// print the result
printArray (num, n);
}
}
// A utility function to check if num has all 9s
int AreAll9s( int* num, int n )
{
int i;
for( i = 0; i < n; ++i )
if( num[i] != 9 )
return 0;
return 1;
}
/* Utility that prints out an array on a line */
void printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver Program to test above function
int main()
{
int num[] = {9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2};
int n = sizeof (num)/ sizeof(num[0]);
generateNextPalindrome( num, n );
return 0;
}
Java
// Java program to find next smallest
// palindrome
public class nextplaindrome
{
// Returns next palindrome of a given
// number num[]. This function is for
// input type 2 and 3
static void generateNextPalindromeUtil(int num[], int n)
{
int mid = n / 2;
// end of left side is always 'mid -1'
int i = mid - 1;
// Beginning of right side depends
// if n is odd or even
int j = (n % 2 == 0) ? mid : mid + 1;
// A bool variable to check if copy of left
// side to right
// is sufficient or not
boolean leftsmaller = false;
// Initially, ignore the middle same digits
while (i >= 0 && num[i] == num[j])
{
i--;
j++;
}
// Find if the middle digit(s) need to
// be incremented or not (or copying left
// side is not sufficient)
if (i < 0 || num[i] < num[j])
{
leftsmaller = true;
}
// Copy the mirror of left to tight
while (i >= 0)
{
num[j++] = num[i--];
}
// Handle the case where middle digit(s)
// must be incremented. This part of code
// is for CASE 1 and CASE 2.2
if (leftsmaller)
{
int carry = 1;
// If there are odd digits, then increment
// the middle digit and store the carry
if (n % 2 == 1) {
num[mid] += 1;
carry = num[mid] / 10;
num[mid] %= 10;
}
i = mid - 1;
j = (n % 2 == 0 ? mid : mid + 1);
// Add 1 to the rightmost digit of the left
// side, propagate the carry towards MSB digit
// and simultaneously copying mirror of the
// left side to the right side.
//when carry is zero no need to loop through till i>=0
while (i >= 0 && carry>0)
{
num[i] = num[i] + carry;
carry = num[i] / 10;
num[i] %= 10;
num[j] = num[i];// copy mirror to right
i--;
j++;
}
}
}
// The function that prints next palindrome
// of a given number num[] with n digits.
static void generateNextPalindrome(int num[], int n)
{
System.out.println("Next Palindrome is:");
// Input type 1: All the digits are 9,
// simply o/p 1 followed by n-1 0's
// followed by 1.
if (isAll9(num, n)) {
System.out.print("1");
for (int i = 0; i < n - 1; i++)
System.out.print("0");
System.out.println("1");
}
// Input type 2 and 3
else {
generateNextPalindromeUtil(num, n);
printarray(num);
}
}
// A utility function to check if num has all 9s
static boolean isAll9(int num[], int n) {
for (int i = 0; i < n; i++)
if (num[i] != 9)
return false;
return true;
}
/* Utility that prints out an array on a line */
static void printarray(int num[]) {
for (int i = 0; i < num.length; i++)
System.out.print(num[i]);
System.out.println();
}
public static void main(String[] args)
{
int num[] = { 9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2 };
generateNextPalindrome(num, num.length);
}
}
Python3
# Returns next palindrome of a given number num[].
# This function is for input type 2 and 3
def generateNextPalindromeUtil (num, n) :
# find the index of mid digit
mid = int(n/2 )
# A bool variable to check if copy of left
# side to right is sufficient or not
leftsmaller = False
# end of left side is always 'mid -1'
i = mid - 1
# Beginning of right side depends
# if n is odd or even
j = mid + 1 if (n % 2) else mid
# Initially, ignore the middle same digits
while (i >= 0 and num[i] == num[j]) :
i-=1
j+=1
# Find if the middle digit(s) need to be
# incremented or not (or copying left
# side is not sufficient)
if ( i < 0 or num[i] < num[j]):
leftsmaller = True
# Copy the mirror of left to tight
while (i >= 0) :
num[j] = num[i]
j+=1
i-=1
# Handle the case where middle
# digit(s) must be incremented.
# This part of code is for CASE 1 and CASE 2.2
if (leftsmaller == True) :
carry = 1
i = mid - 1
# If there are odd digits, then increment
# the middle digit and store the carry
if (n%2 == 1) :
num[mid] += carry
carry = int(num[mid] / 10 )
num[mid] %= 10
j = mid + 1
else:
j = mid
# Add 1 to the rightmost digit of the
# left side, propagate the carry
# towards MSB digit and simultaneously
# copying mirror of the left side
# to the right side.
while (i >= 0) :
num[i] += carry
carry = int(num[i] / 10)
num[i] %= 10
num[j] = num[i] # copy mirror to right
j+=1
i-=1
# The function that prints next
# palindrome of a given number num[]
# with n digits.
def generateNextPalindrome(num, n ) :
print("\nNext palindrome is:")
# Input type 1: All the digits are 9, simply o/p 1
# followed by n-1 0's followed by 1.
if( AreAll9s( num, n ) == True) :
print( "1")
for i in range(1, n):
print( "0" )
print( "1")
# Input type 2 and 3
else:
generateNextPalindromeUtil ( num, n )
# print the result
printArray (num, n)
# A utility function to check if num has all 9s
def AreAll9s(num, n ):
for i in range(1, n):
if( num[i] != 9 ) :
return 0
return 1
# Utility that prints out an array on a line
def printArray(arr, n):
for i in range(0, n):
print(int(arr[i]),end=" ")
print()
# Driver Program to test above function
if __name__ == "__main__":
num = [9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2]
n = len(num)
generateNextPalindrome( num, n )
# This code is contributed by Smitha Dinesh Semwal
C#
// C# program to find next smallest palindrome
using System;
public class GFG {
// Returns next palindrome of a given
// number num[]. This function is for
// input type 2 and 3
static void generateNextPalindromeUtil(int []num, int n)
{
int mid = n / 2;
// end of left side is always 'mid -1'
int i = mid - 1;
// Beginning of right side depends
// if n is odd or even
int j = (n % 2 == 0) ? mid : mid + 1;
// A bool variable to check if copy of left
// side to right
// is sufficient or not
bool leftsmaller = false;
// Initially, ignore the middle same digits
while (i >= 0 && num[i] == num[j])
{
i--;
j++;
}
// Find if the middle digit(s) need to
// be incremented or not (or copying left
// side is not sufficient)
if (i < 0 || num[i] < num[j])
{
leftsmaller = true;
}
// Copy the mirror of left to tight
while (i >= 0)
{
num[j++] = num[i--];
}
// Handle the case where middle digit(s)
// must be incremented. This part of code
// is for CASE 1 and CASE 2.2
if (leftsmaller)
{
int carry = 1;
// If there are odd digits, then increment
// the middle digit and store the carry
if (n % 2 == 1) {
num[mid] += 1;
carry = num[mid] / 10;
num[mid] %= 10;
}
i = mid - 1;
j = (n % 2 == 0 ? mid : mid + 1);
// Add 1 to the rightmost digit of the left
// side, propagate the carry towards MSB digit
// and simultaneously copying mirror of the
// left side to the right side.
while (i >= 0)
{
num[i] = num[i] + carry;
carry = num[i] / 10;
num[i] %= 10;
num[j] = num[i];// copy mirror to right
i--;
j++;
}
}
}
// The function that prints next palindrome
// of a given number num[] with n digits.
static void generateNextPalindrome(int []num, int n)
{
Console.WriteLine("Next Palindrome is:");
// Input type 1: All the digits are 9,
// simply o/p 1 followed by n-1 0's
// followed by 1.
if (isAll9(num, n)) {
Console.Write("1");
for (int i = 0; i < n - 1; i++)
Console.Write("0");
Console.Write("1");
}
// Input type 2 and 3
else {
generateNextPalindromeUtil(num, n);
printarray(num);
}
}
// A utility function to check if num has all 9s
static bool isAll9(int[] num, int n) {
for (int i = 0; i < n; i++)
if (num[i] != 9)
return false;
return true;
}
/* Utility that prints out an array on a line */
static void printarray(int []num) {
for (int i = 0; i < num.Length; i++)
Console.Write(num[i]+ " ");
Console.Write(" ");
}
// Driver code
public static void Main()
{
int []num = { 9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2 };
generateNextPalindrome(num, num.Length);
}
}
// This code is contributed by Smitha.
PHP
<?php
// PHP program to find next
// smallest palindrome
// Returns next palindrome
// of a given number num[].
// This function is for
// input type 2 and 3
function generateNextPalindromeUtil($num, $n)
{
$mid = (int)($n / 2);
// end of left side
// is always 'mid -1'
$i = $mid - 1;
// Beginning of right
// side depends if n
// is odd or even
$j = ($n % 2 == 0) ?
$mid : ($mid + 1);
// A bool variable to check
// if copy of left side to
// right is sufficient or not
$leftsmaller = false;
// Initially, ignore the
// middle same digits
while ($i >= 0 &&
$num[$i] == $num[$j])
{
$i--;
$j++;
}
// Find if the middle digit(s)
// need to be incremented or
// not (or copying left side
// is not sufficient)
if ($i < 0 || $num[$i] < $num[$j])
{
$leftsmaller = true;
}
// Copy the mirror
// of left to tight
while ($i >= 0)
{
$num[$j++] = $num[$i--];
}
// Handle the case where
// middle digit(s) must be
// incremented. This part
// of code is for CASE 1
// and CASE 2.2
if ($leftsmaller)
{
$carry = 1;
// If there are odd digits,
// then increment the middle
// digit and store the carry
if ($n % 2 == 1)
{
$num[$mid] += 1;
$carry = (int)($num[$mid] / 10);
$num[$mid] %= 10;
}
$i = $mid - 1;
$j = ($n % 2 == 0 ?
$mid : $mid + 1);
// Add 1 to the rightmost digit
// of the left side, propagate
// the carry towards MSB digit
// and simultaneously copying
// mirror of the left side to
// the right side.
while ($i >= 0)
{
$num[$i] = $num[$i] + $carry;
$carry = (int)($num[$i] / 10);
$num[$i] %= 10;
// copy mirror to right
$num[$j] = $num[$i];
$i--;
$j++;
}
}
return $num;
}
// The function that prints
// next palindrome of a given
// number num[] with n digits.
function generateNextPalindrome($num, $n)
{
echo "Next Palindrome is:\n";
// Input type 1: All the
// digits are 9, simply
// o/p 1 followed by n-1
// 0's followed by 1.
if (isAll9($num, $n))
{
echo "1";
for ($i = 0; $i < $n - 1; $i++)
echo "0";
echo "1";
}
// Input type 2 and 3
else
{
$num = generateNextPalindromeUtil($num, $n);
printarray($num);
}
}
// A utility function to
// check if num has all 9s
function isAll9($num, $n)
{
for ($i = 0; $i < $n; $i++)
if ($num[$i] != 9)
return false;
return true;
}
/* Utility that prints out
an array on a line */
function printarray($num)
{
for ($i = 0;
$i < count($num); $i++)
echo $num[$i];
echo "\n";
}
// Driver code
$num = array(9, 4, 1, 8, 7,
9, 7, 8, 3, 2, 2);
generateNextPalindrome($num,
count($num));
// This code is contributed by mits.
?>
Javascript
<script>
// JavaScript program to find next smallest
// palindrome
// Returns next palindrome of a given
// number num. This function is for
// input type 2 and 3
function generateNextPalindromeUtil(num , n)
{
var mid = parseInt(n / 2);
// end of left side is always 'mid -1'
var i = mid - 1;
// Beginning of right side depends
// if n is odd or even
var j = (n % 2 == 0) ? mid : mid + 1;
// A bool variable to check if copy of left
// side to right
// is sufficient or not
leftsmaller = false;
// Initially, ignore the middle same digits
while (i >= 0 && num[i] == num[j])
{
i--;
j++;
}
// Find if the middle digit(s) need to
// be incremented or not (or copying left
// side is not sufficient)
if (i < 0 || num[i] < num[j])
{
leftsmaller = true;
}
// Copy the mirror of left to tight
while (i >= 0)
{
num[j++] = num[i--];
}
// Handle the case where middle digit(s)
// must be incremented. This part of code
// is for CASE 1 and CASE 2.2
if (leftsmaller)
{
var carry = 1;
// If there are odd digits, then increment
// the middle digit and store the carry
if (n % 2 == 1) {
num[mid] += 1;
carry = parseInt(num[mid] / 10);
num[mid] %= 10;
}
i = mid - 1;
j = (n % 2 == 0 ? mid : mid + 1);
// Add 1 to the rightmost digit of the left
// side, propagate the carry towards MSB digit
// and simultaneously copying mirror of the
// left side to the right side.
//when carry is zero no need to loop through till i>=0
while (i >= 0 && carry>0)
{
num[i] = num[i] + carry;
carry = parseInt(num[i] / 10);
num[i] %= 10;
num[j] = num[i];// copy mirror to right
i--;
j++;
}
}
}
// The function that prints next palindrome
// of a given number num with n digits.
function generateNextPalindrome(num , n)
{
document.write("Next Palindrome is: <br>");
// Input type 1: All the digits are 9,
// simply o/p 1 followed by n-1 0's
// followed by 1.
if (isAll9(num, n)) {
document.write("1");
for (i = 0; i < n - 1; i++)
document.write("0");
document.write("1");
}
// Input type 2 and 3
else {
generateNextPalindromeUtil(num, n);
printarray(num);
}
}
// A utility function to check if num has all 9s
function isAll9(num , n) {
for (i = 0; i < n; i++)
if (num[i] != 9)
return false;
return true;
}
/* Utility that prints out an array on a line */
function printarray(num) {
for (i = 0; i < num.length; i++)
document.write(num[i]+"\n");
}
var num = [ 9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2 ];
generateNextPalindrome(num, num.length);
// This code is contributed by 29AjayKumar
</script>
Producción
Next palindrome is:9 4 1 8 8 0 8 8 1 4 9
Complejidad de tiempo: O(num)
Complejidad espacial: O(1)
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA