Next higher palindromic number using the same set of digits | function to reverse the digits in the range i to j in 'num ; function to find next higher palindromic number using the same set of digits ; if length of number is less than '3' then no higher palindromic number can be formed ; find the index of last digit in the 1 st half of 'num ; Start from the ( mid - 1 ) th digit and find the first digit that is smaller than the digit next to it . ; 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 ; Find the smallest digit on right side of ith digit which is greater than num [ i ] up to index 'mid ; swap num [ i ] with num [ smallest ] ; as the number is a palindrome , the same swap of digits should be performed in the 2 nd half of 'num ; reverse digits in the range ( i + 1 ) to mid ; if n is even , then reverse digits in the range mid + 1 to n - i - 2 ; else if n is odd , then reverse digits in the range mid + 2 to n - i - 2 ; required next higher palindromic number ; Driver Code
' NEW_LINE def reverse ( num , i , j ) : NEW_LINE INDENT while ( i < j ) : NEW_LINE INDENT temp = num [ i ] NEW_LINE num [ i ] = num [ j ] NEW_LINE num [ j ] = temp NEW_LINE i = i + 1 NEW_LINE j = j - 1 NEW_LINE DEDENT DEDENT def nextPalin ( num , n ) : NEW_LINE INDENT if ( n <= 3 ) : NEW_LINE INDENT print " Not ▁ Possible " NEW_LINE return NEW_LINE DEDENT DEDENT ' NEW_LINE INDENT mid = n / 2 - 1 NEW_LINE i = mid - 1 NEW_LINE while i >= 0 : NEW_LINE INDENT if ( num [ i ] < num [ i + 1 ] ) : NEW_LINE INDENT break NEW_LINE DEDENT i = i - 1 NEW_LINE DEDENT if ( i < 0 ) : NEW_LINE INDENT print " Not ▁ Possible " NEW_LINE return NEW_LINE DEDENT DEDENT ' NEW_LINE INDENT smallest = i + 1 NEW_LINE j = i + 2 NEW_LINE while j <= mid : NEW_LINE INDENT if ( num [ j ] > num [ i ] and num [ j ] < num [ smallest ] ) : NEW_LINE INDENT smallest = j NEW_LINE DEDENT j = j + 1 NEW_LINE DEDENT temp = num [ i ] NEW_LINE num [ i ] = num [ smallest ] NEW_LINE num [ smallest ] = temp NEW_LINE DEDENT ' NEW_LINE INDENT temp = num [ n - i - 1 ] NEW_LINE num [ n - i - 1 ] = num [ n - smallest - 1 ] NEW_LINE num [ n - smallest - 1 ] = temp NEW_LINE reverse ( num , i + 1 , mid ) NEW_LINE if ( n % 2 == 0 ) : NEW_LINE INDENT reverse ( num , mid + 1 , n - i - 2 ) NEW_LINE DEDENT else : NEW_LINE INDENT reverse ( num , mid + 2 , n - i - 2 ) NEW_LINE DEDENT result = ' ' . join ( num ) NEW_LINE print " Next ▁ Palindrome : ▁ " , result NEW_LINE DEDENT st = "4697557964" NEW_LINE num = list ( st ) NEW_LINE n = len ( st ) NEW_LINE nextPalin ( num , n ) NEW_LINE