Given a palindromic number num having n number of digits. The problem is to find the smallest palindromic number greater than num using the same set of digits as in num. If no such number can be formed then print “Not Possible”.
The number could be very large and may or may not even fit into long long int.
Examples:
Input : 4697557964
Output : 4756996574
Input : 543212345
Output : Not Possible
Approach:
Follow the below steps to solve the problem:
- If number of digits n <= 3, then print “Not Possible” and return.
- Calculate mid = n/2 – 1.
- Start traversing from the digit at index mid up to the 1st digit and while traversing find the index i of the rightmost digit which is smaller than the digit on its right side.
- Now search for the smallest digit greater than the digit num[i] in the index range i+1 to mid. Let the index of this digit be smallest.
- If no such smallest digit found, then print “Not Possible”.
- Else the swap the digits at index i and smallest and also swap the digits at index n-i-1 and n-smallest-1. This step is done so as to maintain the palindromic property in num.
- Now reverse the digits in the index range i+1 to mid. Also If n is even then reverse the digits in the index range mid+1 to n-i-2 else if n is odd then reverse the digits in the index range mid+2 to n-i-2. This step is done so as to maintain the palindromic property in num.
- Print the final modified number num.
Implementation:
C
#include <stdio.h>
#include <string.h>
void reverse( char num[], int i, int j)
{
while (i < j) {
char temp = num[i];
num[i] = num[j];
num[j] = temp;
i++;
j--;
}
}
void nextPalin( char num[], int n)
{
if (n <= 3) {
printf ( "Not Possible" );
return ;
}
int mid = n / 2 - 1;
int i, j;
for (i = mid - 1; i >= 0; i--)
if (num[i] < num[i + 1])
break ;
if (i < 0) {
printf ( "Not Possible" );
return ;
}
int smallest = i + 1;
for (j = i + 2; j <= mid; j++)
if (num[j] > num[i] && num[j] <= num[smallest])
smallest = j;
char temp = num[i];
num[i] = num[smallest];
num[smallest] = temp;
temp = num[n - i - 1];
num[n - i - 1] = num[n - smallest - 1];
num[n - smallest - 1] = temp;
reverse(num, i + 1, mid);
if (n % 2 == 0)
reverse(num, mid + 1, n - i - 2);
else
reverse(num, mid + 2, n - i - 2);
printf ( "Next Palindrome: %s" , num);
}
int main()
{
char num[] = "4697557964" ;
int n = strlen (num);
nextPalin(num, n);
return 0;
}
|
C++
#include <bits/stdc++.h>
using namespace std;
void reverse( char num[], int i, int j)
{
while (i < j) {
swap(num[i], num[j]);
i++;
j--;
}
}
void nextPalin( char num[], int n)
{
if (n <= 3) {
cout << "Not Possible" ;
return ;
}
int mid = n / 2 - 1;
int i, j;
for (i = mid - 1; i >= 0; i--)
if (num[i] < num[i + 1])
break ;
if (i < 0) {
cout << "Not Possible" ;
return ;
}
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], num[smallest]);
swap(num[n - i - 1], num[n - smallest - 1]);
reverse(num, i + 1, mid);
if (n % 2 == 0)
reverse(num, mid + 1, n - i - 2);
else
reverse(num, mid + 2, n - i - 2);
cout << "Next Palindrome: "
<< num;
}
int main()
{
char num[] = "4697557964" ;
int n = strlen (num);
nextPalin(num, n);
return 0;
}
|
Java
import java.util.*;
class NextHigherPalindrome
{
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--;
}
}
public static void nextPalin( char num[], int n)
{
if (n <= 3 ) {
System.out.println( "Not Possible" );
return ;
}
char temp;
int mid = n / 2 - 1 ;
int i, j;
for (i = mid - 1 ; i >= 0 ; i--)
if (num[i] < num[i + 1 ])
break ;
if (i < 0 ) {
System.out.println( "Not Possible" );
return ;
}
int smallest = i + 1 ;
for (j = i + 2 ; j <= mid; j++)
if (num[j] > num[i] &&
num[j] <= num[smallest])
smallest = j;
temp = num[i];
num[i] = num[smallest];
num[smallest] = temp;
temp = num[n - i - 1 ];
num[n - i - 1 ] = num[n - smallest - 1 ];
num[n - smallest - 1 ] = temp;
reverse(num, i + 1 , mid);
if (n % 2 == 0 )
reverse(num, mid + 1 , n - i - 2 );
else
reverse(num, mid + 2 , n - i - 2 );
String result=String.valueOf(num);
System.out.println( "Next Palindrome: " +
result);
}
public static void main(String args[])
{
String str= "4697557964" ;
char num[]=str.toCharArray();
int n=str.length();
nextPalin(num,n);
}
}
|
Python
def reverse(num, i, j) :
while (i < j) :
temp = num[i]
num[i] = num[j]
num[j] = temp
i = i + 1
j = j - 1
def nextPalin(num, n) :
if (n < = 3 ) :
print "Not Possible"
return
mid = n / 2 - 1
i = mid - 1
while i > = 0 :
if (num[i] < num[i + 1 ]) :
break
i = i - 1
if (i < 0 ) :
print "Not Possible"
return
smallest = i + 1
j = i + 2
while j < = mid :
if (num[j] > num[i] and num[j] <
num[smallest]) :
smallest = j
j = j + 1
temp = num[i]
num[i] = num[smallest]
num[smallest] = temp
temp = num[n - i - 1 ]
num[n - i - 1 ] = num[n - smallest - 1 ]
num[n - smallest - 1 ] = temp
reverse(num, i + 1 , mid)
if (n % 2 = = 0 ) :
reverse(num, mid + 1 , n - i - 2 )
else :
reverse(num, mid + 2 , n - i - 2 )
result = ''.join(num)
print "Next Palindrome: " ,result
st = "4697557964"
num = list (st)
n = len (st)
nextPalin(num, n)
|
C#
using System;
class GFG
{
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--;
}
}
public static void nextPalin( char [] num,
int n)
{
if (n <= 3)
{
Console.WriteLine( "Not Possible" );
return ;
}
char temp;
int mid = n / 2 - 1;
int i, j;
for (i = mid - 1; i >= 0; i--)
if (num[i] < num[i + 1])
break ;
if (i < 0)
{
Console.WriteLine( "Not Possible" );
return ;
}
int smallest = i + 1;
for (j = i + 2; j <= mid; j++)
if (num[j] > num[i] &&
num[j] < num[smallest])
smallest = j;
temp = num[i];
num[i] = num[smallest];
num[smallest] = temp;
temp = num[n - i - 1];
num[n - i - 1] = num[n - smallest - 1];
num[n - smallest - 1] = temp;
reverse(num, i + 1, mid);
if (n % 2 == 0)
reverse(num, mid + 1,
n - i - 2);
else
reverse(num, mid + 2,
n - i - 2);
String result = new String(num);
Console.WriteLine( "Next Palindrome: " +
result);
}
public static void Main()
{
String str = "4697557964" ;
char [] num = str.ToCharArray();
int n = str.Length;
nextPalin(num, n);
}
}
|
PHP
<?php
function reverse(& $num , $i , $j )
{
while ( $i < $j )
{
$t = $num [ $i ];
$num [ $i ] = $num [ $j ];
$num [ $j ] = $t ;
$i ++;
$j --;
}
}
function nextPalin( $num , $n )
{
if ( $n <= 3)
{
echo "Not Possible" ;
return ;
}
$mid = ( $n / 2) - 1;
$i = $mid - 1;
$j ;
for (; $i >= 0; $i --)
if ( $num [ $i ] < $num [ $i + 1])
break ;
if ( $i < 0)
{
echo "Not Possible" ;
return ;
}
$smallest = $i + 1;
$j = 0;
for ( $j = $i + 2; $j <= $mid ; $j ++)
if ( $num [ $j ] > $num [ $i ] &&
$num [ $j ] < $num [ $smallest ])
$smallest = $j ;
$t = $num [ $i ];
$num [ $i ] = $num [ $smallest ];
$num [ $smallest ] = $t ;
$t = $num [ $n - $i - 1];
$num [ $n - $i - 1] = $num [ $n - $smallest - 1];
$num [ $n - $smallest - 1] = $t ;
reverse( $num , $i + 1, $mid );
if ( $n % 2 == 0)
reverse( $num , $mid + 1, $n - $i - 2);
else
reverse( $num , $mid + 2, $n - $i - 2);
echo "Next Palindrome: " . $num ;
}
$num = "4697557964" ;
$n = strlen ( $num );
nextPalin( $num , $n );
?>
|
Javascript
<script>
function reverse(num , i, j)
{
while (i < j)
{
var temp = num[i];
num[i] = num[j];
num[j] = temp;
i++;
j--;
}
}
function nextPalin(num, n)
{
if (n <= 3)
{
document.write( "Not Possible" );
return ;
}
var temp;
var mid = n / 2 - 1;
var i, j;
for (i = mid - 1; i >= 0; i--)
if (num[i] < num[i + 1])
break ;
if (i < 0)
{
document.write( "Not Possible" );
return ;
}
var smallest = i + 1;
for (j = i + 2; j <= mid; j++)
if (num[j] > num[i] &&
num[j] <= num[smallest])
smallest = j;
temp = num[i];
num[i] = num[smallest];
num[smallest] = temp;
temp = num[n - i - 1];
num[n - i - 1] = num[n - smallest - 1];
num[n - smallest - 1] = temp;
reverse(num, i + 1, mid);
if (n % 2 == 0)
reverse(num, mid + 1, n - i - 2);
else
reverse(num, mid + 2, n - i - 2);
var result = num.join( '' );
document.write( "Next Palindrome: " +
result);
}
var str = "4697557964" ;
var num = str.split( '' );
var n = str.length;
nextPalin(num,n);
</script>
|
Output
Next Palindrome: 4756996574
Time Complexity: O(n)
Auxiliary Space: O(1)
If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!