Dado un número palindrómico num que tiene n número de dígitos. El problema es encontrar el número palindrómico más pequeño mayor que num usando el mismo conjunto de dígitos que en num . Si no se puede formar dicho número, escriba «No es posible».
El número podría ser muy grande y puede o no encajar en long long int.
Ejemplos:
Input : 4697557964 Output : 4756996574 Input : 543212345 Output : Not Possible
Enfoque: Los siguientes son los pasos.
- Si el número de dígitos n <= 3, imprima «No posible» y regrese.
- Calcular mid = n/2 – 1.
- Comience a atravesar desde el dígito en el índice medio hasta el primer dígito y, mientras atraviesa, encuentre el índice i del dígito más a la derecha que es más pequeño que el dígito en su lado derecho.
- Ahora busque el dígito más pequeño mayor que el dígito num[i] en el rango de índice i+1 a mid . Sea el índice de este dígito el más pequeño .
- Si no se encuentra el dígito más pequeño, imprima «No es posible».
- De lo contrario, intercambie los dígitos en el índice i y el más pequeño y también intercambie los dígitos en el índice ni-1 y n-smallest-1 . Este paso se realiza para mantener la propiedad palindrómica en núm .
- Ahora invierta los dígitos en el rango de índice i+1 a mid . Además, si n es par, invierta los dígitos en el rango de índice mid+1 a ni-2; de lo contrario, si n es impar, invierta los dígitos en el rango de índice mid+2 a ni-2 . Este paso se realiza para mantener la propiedad palindrómica en núm .
- Imprime el número modificado final num .
Implementación:
C++
// C++ implementation to find next higher
// palindromic number using the same set
// of digits
#include <bits/stdc++.h>
using namespace std;
// function to reverse the digits in the
// range i to j in 'num'
void reverse(char num[], int i, int j)
{
while (i < j) {
swap(num[i], num[j]);
i++;
j--;
}
}
// function to find next higher palindromic
// number using the same set of digits
void nextPalin(char num[], int n)
{
// if length of number is less than '3'
// then no higher palindromic number
// can be formed
if (n <= 3) {
cout << "Not Possible";
return;
}
// find the index of last digit
// in the 1st half of 'num'
int mid = n / 2 - 1;
int i, j;
// Start from the (mid-1)th digit and
// find the first digit that is
// smaller than the digit next to it.
for (i = mid - 1; i >= 0; i--)
if (num[i] < num[i + 1])
break;
// If no such digit is found, then all
// digits are in descending order which
// means there cannot be a greater
// palindromic number with same set of
// digits
if (i < 0) {
cout << "Not Possible";
return;
}
// Find the smallest digit on right
// side of ith digit which is greater
// than num[i] up to index 'mid'
int smallest = i + 1;
for (j = i + 2; j <= mid; j++)
if (num[j] > num[i] &&
num[j] <= num[smallest])
smallest = j;
// swap num[i] with num[smallest]
swap(num[i], num[smallest]);
// as the number is a palindrome, the same
// swap of digits should be performed in
// the 2nd half of 'num'
swap(num[n - i - 1], num[n - smallest - 1]);
// reverse digits in the range (i+1) to mid
reverse(num, i + 1, mid);
// if n is even, then reverse digits in the
// range mid+1 to n-i-2
if (n % 2 == 0)
reverse(num, mid + 1, n - i - 2);
// else if n is odd, then reverse digits
// in the range mid+2 to n-i-2
else
reverse(num, mid + 2, n - i - 2);
// required next higher palindromic number
cout << "Next Palindrome: "
<< num;
}
// Driver program to test above
int main()
{
char num[] = "4697557964";
int n = strlen(num);
nextPalin(num, n);
return 0;
}
Java
// Java implementation to find next higher
// palindromic number using the same set
// of digits
import java.util.*;
class NextHigherPalindrome
{
// function to reverse the digits in the
// range i to j in 'num'
public static void reverse(char num[], int i,
int j)
{
while (i < j) {
char temp = num[i];
num[i] = num[j];
num[j] = temp;
i++;
j--;
}
}
// function to find next higher palindromic
// number using the same set of digits
public static void nextPalin(char num[], int n)
{
// if length of number is less than '3'
// then no higher palindromic number
// can be formed
if (n <= 3) {
System.out.println("Not Possible");
return;
}
char temp;
// find the index of last digit
// in the 1st half of 'num'
int mid = n / 2 - 1;
int i, j;
// Start from the (mid-1)th digit and
// find the first digit that is
// smaller than the digit next to it.
for (i = mid - 1; i >= 0; i--)
if (num[i] < num[i + 1])
break;
// If no such digit is found, then all
// digits are in descending order which
// means there cannot be a greater
// palindromic number with same set of
// digits
if (i < 0) {
System.out.println("Not Possible");
return;
}
// Find the smallest digit on right
// side of ith digit which is greater
// than num[i] up to index 'mid'
int smallest = i + 1;
for (j = i + 2; j <= mid; j++)
if (num[j] > num[i] &&
num[j] <= num[smallest])
smallest = j;
// swap num[i] with num[smallest]
temp = num[i];
num[i] = num[smallest];
num[smallest] = temp;
// as the number is a palindrome,
// the same swap of digits should
// be performed in the 2nd half of
// 'num'
temp = num[n - i - 1];
num[n - i - 1] = num[n - smallest - 1];
num[n - smallest - 1] = temp;
// reverse digits in the range (i+1)
// to mid
reverse(num, i + 1, mid);
// if n is even, then reverse
// digits in the range mid+1 to
// n-i-2
if (n % 2 == 0)
reverse(num, mid + 1, n - i - 2);
// else if n is odd, then reverse
// digits in the range mid+2 to n-i-2
else
reverse(num, mid + 2, n - i - 2);
// required next higher palindromic
// number
String result=String.valueOf(num);
System.out.println("Next Palindrome: "+
result);
}
// Driver Code
public static void main(String args[])
{
String str="4697557964";
char num[]=str.toCharArray();
int n=str.length();
nextPalin(num,n);
}
}
// This code is contributed by Danish Kaleem
Python
# Python implementation to find next higher # palindromic number using the same set # of digits # function to reverse the digits in the # range i to j in 'num' def reverse(num, i, j) : while (i < j) : temp = num[i] num[i] = num[j] num[j] = temp i = i + 1 j = j - 1 # function to find next higher palindromic # number using the same set of digits def nextPalin(num, n) : # if length of number is less than '3' # then no higher palindromic number # can be formed if (n <= 3) : print "Not Possible" return # find the index of last digit # in the 1st half of 'num' mid = n / 2 - 1 # Start from the (mid-1)th digit and # find the first digit that is # smaller than the digit next to it. i = mid - 1 while i >= 0 : if (num[i] < num[i + 1]) : break i = i - 1 # If no such digit is found, then all # digits are in descending order which # means there cannot be a greater # palindromic number with same set of # digits if (i < 0) : print "Not Possible" return # Find the smallest digit on right # side of ith digit which is greater # than num[i] up to index 'mid' smallest = i + 1 j = i + 2 while j <= mid : if (num[j] > num[i] and num[j] < num[smallest]) : smallest = j j = j + 1 # swap num[i] with num[smallest] temp = num[i] num[i] = num[smallest] num[smallest] = temp # as the number is a palindrome, # the same swap of digits should # be performed in the 2nd half of # 'num' temp = num[n - i - 1] num[n - i - 1] = num[n - smallest - 1] num[n - smallest - 1] = temp # reverse digits in the range (i+1) # to mid reverse(num, i + 1, mid) # if n is even, then reverse # digits in the range mid+1 to # n-i-2 if (n % 2 == 0) : reverse(num, mid + 1, n - i - 2) # else if n is odd, then reverse # digits in the range mid+2 to n-i-2 else : reverse(num, mid + 2, n - i - 2) # required next higher palindromic # number result = ''.join(num) print "Next Palindrome: ",result # Driver Code st = "4697557964" num = list(st) n = len(st) nextPalin(num, n) # This code is contributed by Nikita Tiwari
C#
// C# implementation to find
// next higher palindromic
// number using the same set
// of digits
using System;
class GFG
{
// function to reverse
// the digits in the
// range i to j in 'num'
public static void reverse(char[] num,
int i, int j)
{
while (i < j)
{
char temp = num[i];
num[i] = num[j];
num[j] = temp;
i++;
j--;
}
}
// function to find next
// higher palindromic number
// using the same set of digits
public static void nextPalin(char[] num,
int n)
{
// if length of number is
// less than '3' then no
// higher palindromic number
// can be formed
if (n <= 3)
{
Console.WriteLine("Not Possible");
return;
}
char temp;
// find the index of last
// digit in the 1st half
// of 'num'
int mid = n / 2 - 1;
int i, j;
// Start from the (mid-1)th
// digit and find the
// first digit that is
// smaller than the digit
// next to it.
for (i = mid - 1; i >= 0; i--)
if (num[i] < num[i + 1])
break;
// If no such digit is found,
// then all digits are in
// descending order which
// means there cannot be a
// greater palindromic number
// with same set of digits
if (i < 0)
{
Console.WriteLine("Not Possible");
return;
}
// Find the smallest digit on
// right side of ith digit
// which is greater than num[i]
// up to index 'mid'
int smallest = i + 1;
for (j = i + 2; j <= mid; j++)
if (num[j] > num[i] &&
num[j] < num[smallest])
smallest = j;
// swap num[i] with
// num[smallest]
temp = num[i];
num[i] = num[smallest];
num[smallest] = temp;
// as the number is a palindrome,
// the same swap of digits should
// be performed in the 2nd half of
// 'num'
temp = num[n - i - 1];
num[n - i - 1] = num[n - smallest - 1];
num[n - smallest - 1] = temp;
// reverse digits in the
// range (i+1) to mid
reverse(num, i + 1, mid);
// if n is even, then
// reverse digits in the
// range mid+1 to n-i-2
if (n % 2 == 0)
reverse(num, mid + 1,
n - i - 2);
// else if n is odd, then
// reverse digits in the
// range mid+2 to n-i-2
else
reverse(num, mid + 2,
n - i - 2);
// required next higher
// palindromic number
String result = new String(num);
Console.WriteLine("Next Palindrome: "+
result);
}
// Driver Code
public static void Main()
{
String str = "4697557964";
char[] num = str.ToCharArray();
int n = str.Length;
nextPalin(num, n);
}
}
// This code is contributed by mits
PHP
<?php
// PHP implementation to find
// next higher palindromic number
// using the same set of digits
// function to reverse the digits
// in the range i to j in 'num'
function reverse(&$num, $i, $j)
{
while ($i < $j)
{
$t = $num[$i];
$num[$i] = $num[$j];
$num[$j] = $t;
$i++;
$j--;
}
}
// function to find next higher
// palindromic number using the
// same set of digits
function nextPalin($num, $n)
{
// if length of number is less
// than '3' then no higher
// palindromic number can be formed
if ($n <= 3)
{
echo "Not Possible";
return;
}
// find the index of last digit
// in the 1st half of 'num'
$mid = ($n / 2) - 1;
$i = $mid - 1;
$j;
// Start from the (mid-1)th digit
// and find the first digit
// that is smaller than the digit
// next to it.
for (; $i >= 0; $i--)
if ($num[$i] < $num[$i + 1])
break;
// If no such digit is found,
// then all digits are in
// descending order which means
// there cannot be a greater
// palindromic number with same
// set of digits
if ($i < 0)
{
echo "Not Possible";
return;
}
// Find the smallest digit on right
// side of ith digit which is greater
// than num[i] up to index 'mid'
$smallest = $i + 1;
$j = 0;
for ($j = $i + 2; $j <= $mid; $j++)
if ($num[$j] > $num[$i] &&
$num[$j] < $num[$smallest])
$smallest = $j;
// swap num[i] with num[smallest]
$t = $num[$i];
$num[$i] = $num[$smallest];
$num[$smallest] = $t;
// as the number is a palindrome,
// the same swap of digits should
// be performed in the 2nd half of 'num'
$t = $num[$n - $i - 1];
$num[$n - $i - 1] = $num[$n - $smallest - 1];
$num[$n - $smallest - 1] = $t;
// reverse digits in the
// range (i+1) to mid
reverse($num, $i + 1, $mid);
// if n is even, then
// reverse digits in the
// range mid+1 to n-i-2
if ($n % 2 == 0)
reverse($num, $mid + 1, $n - $i - 2);
// else if n is odd, then reverse
// digits in the range mid+2
// to n-i-2
else
reverse($num, $mid + 2, $n - $i - 2);
// required next higher
// palindromic number
echo "Next Palindrome: " . $num;
}
// Driver Code
$num = "4697557964";
$n = strlen($num);
nextPalin($num, $n);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript implementation to find next higher
// palindromic number using the same set
// of digitsclass NextHigherPalindrome
// Function to reverse the digits in the
// range i to j in 'num'
function reverse(num , i, j)
{
while (i < j)
{
var temp = num[i];
num[i] = num[j];
num[j] = temp;
i++;
j--;
}
}
// Function to find next higher palindromic
// number using the same set of digits
function nextPalin(num, n)
{
// If length of number is less than '3'
// then no higher palindromic number
// can be formed
if (n <= 3)
{
document.write("Not Possible");
return;
}
var temp;
// Find the index of last digit
// in the 1st half of 'num'
var mid = n / 2 - 1;
var i, j;
// Start from the (mid-1)th digit and
// find the first digit that is
// smaller than the digit next to it.
for(i = mid - 1; i >= 0; i--)
if (num[i] < num[i + 1])
break;
// If no such digit is found, then all
// digits are in descending order which
// means there cannot be a greater
// palindromic number with same set of
// digits
if (i < 0)
{
document.write("Not Possible");
return;
}
// Find the smallest digit on right
// side of ith digit which is greater
// than num[i] up to index 'mid'
var smallest = i + 1;
for(j = i + 2; j <= mid; j++)
if (num[j] > num[i] &&
num[j] <= num[smallest])
smallest = j;
// Swap num[i] with num[smallest]
temp = num[i];
num[i] = num[smallest];
num[smallest] = temp;
// As the number is a palindrome,
// the same swap of digits should
// be performed in the 2nd half of
// 'num'
temp = num[n - i - 1];
num[n - i - 1] = num[n - smallest - 1];
num[n - smallest - 1] = temp;
// Reverse digits in the range (i+1)
// to mid
reverse(num, i + 1, mid);
// If n is even, then reverse
// digits in the range mid+1 to
// n-i-2
if (n % 2 == 0)
reverse(num, mid + 1, n - i - 2);
// Else if n is odd, then reverse
// digits in the range mid+2 to n-i-2
else
reverse(num, mid + 2, n - i - 2);
// Required next higher palindromic
// number
var result = num.join('');
document.write("Next Palindrome: "+
result);
}
// Driver Code
var str = "4697557964";
var num = str.split('');
var n = str.length;
nextPalin(num,n);
// This code is contributed by 29AjayKumar
</script>
Producción
Next Palindrome: 4756996574
Complejidad de tiempo: O(n)
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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