Next higher palindromic number using the same set of digits | C ++ 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 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 program to test above
#include <bits/stdc++.h> NEW_LINE 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 ; }