We are given an number and we have to find the smallest pallindrome number greater than N which can be formed by using the same set of digits as in N. Hence, the problem is to rearrange the digits of a number N so that the resulting number is the smallest possible palindrome greater than N.

A palindrome is a number that reads that same from both left and right side like "aadklkdaa".

Examples of our problem statement:

INPUT: 233
OUTPUT: 323

INPUT: 2233
OUTPUT: 2332

INPUT : 323
OUTPUT: 323

INPUT: 123
OUTPUT: NOT POSSIBLE

Naive approach

We can generate all the possible permutation of the digits of the number and find the number which is just greater than N and is also an pallindrome generating permutations of a N digit number requires N! operations and if N is very large then it will result in timeout.

Hence we need to find an efficient algorithm.We can apply greedy approach to the following problem and hence find an efficient solution.

Greedy approach

1. Firstly we need to check if N is itself a Pallindrome if so then we can return the number itself Otherwise,
2. Then we check the frequency of all the characters in the string and if all the characters are appearing even number of times and the length of the string is even then palindrome is possible.
3. Or, if all the characters occur even number of times and only one character occurs odd number of times and the length of the string is odd then the pallindrome is possible
4. Firstly we do for the string with odd length.
   1. We can place the the number which is occuring odd number of times at the mid position of the string becuase it cannot occur at any other position other than the mid position and we decrease the count of that element in the frequency array.
   2. We traverse the string and we place every character of the string in their corresponding position in the answer string from the starting position and from the ending position so that it results in an palindrome and we decrease its count in the frequency array by 2.
5. For the string with even length we follow the same step as in 4) .2 but we skip the 1. step as we do not need it.
6. We return the smallest greater pallindrome number as the result.

Example

INPUT 2233
OUTPUT 2332

Walkthrough the code with the example:

First we maintain a frequency array of the input:

FREQUENCY ARRAY   0 1 2 3 4 5 6 7 8 9 
                   0 0 2 2 0 0 0 0 0 0

We see that every element occurs twice in the input and the length of the input is also even so it is possible to make a pallindrome from the same set of digits.

Hence we traverse through the input and find the first element and make another array of same length of the input and make the first and the last element of the array same as the first element of the input

INPUT NUMBER   2 2 3 3
OUTPUT ARRAY   2 _ _ 2

We decrease the count of the count of the element in the frequnency array by 2.

FREQUENCY ARRAY   0 1 2 3 4 5 6 7 8 9
                  0 0 0 2 0 0 0 0 0 0

Now we check for the next element in the input which has frequency greater than 2 and put it in the 2nd position from the left and the right of the output array.
and decrease its count in the frequency array by 2.

INPUT NUMBER   2 2 3 3
OUTPUT NUMBER  2 3 3 2

We decrease the count of the element in the frequency array by 2.

FREQUENCY ARRAY   0 1 2 3 4 5 6 7 8 9
                  0 0 0 0 0 0 0 0 0 0

Hence we get out ouput number which is the smallest pallindrome number formed by the same set of digits.

INPUT 2233
OUTPUT 2332

Implementation

Following is the C++ implementation of our above approach:

// Part of OpenGenus IQ
#include<iostream>
using namespace std;
int odd=0;
int even=0;

string smallestPallindromicNumber(string n){
    //Calculating the length of the string
    int len=n.length();
    //check if the number is a pallindrome
    int l=len-1;
    bool isPallindrome=false;
    //we will only traverse till half of the string and check for its corresponding character from the end
    int half_length=len/2;
    //if the length of the string is even then we have to check for the mid element
    if(len%2==0){
        half_length--;
    }
    //checking if the number is a pallindrome
    for(int i=0;i<=half_length;i++){
        if(n[i]==n[l]){
            isPallindrome=true;
        }else{
            isPallindrome=false;
            break;
        }
        l--;
    }
    //if the number is a pallindrome then we return the number as it is the smallest
    if(isPallindrome){
       return n;
    }else{
    //if the number is not a pallindrome
    int arr[10]={0};
    //calculating the frequency array of the string
    for(int i=0;i<len;i++){
        arr[n[i]-'0']++;
    }
    char odd_digit;
    //checking if the palindrome is possible or not
    for(int i=0;i<=9;i++){
        if(arr[i]&1){
            odd++;
            //we are adding 48 to be able to store an integer into an character type variable
            odd_digit=i+48;
        }else{
        even++;}
    }

    //if the array is possible
    if(len&1 && odd==1){
            //we create the array by placing the odd digit in its position
            char ans[1000];
            //ans[len/2]=odd_digit;
            string answer;
            arr[odd_digit-'0']--;
            int j=0;
            // we are filling the answer string with the numbers from the original string as far as possible by maintaining it as a pallindrome
            for(int i=0;i<len;i++){
                    //if the position is odd then we need to add the odd element in its place
                    if(j==len/2){
                        ans[j]=odd_digit;
                    }else{
                        //if the element has not been used then we store it in  the answer array
                if(arr[n[i]-'0']>0){
                ans[j]=n[i];
                ans[len-j-1]=n[i];
                arr[n[i]-'0']=arr[n[i]-'0']-2;
                }
                    }
            //incrementing positions for the original string answer array
                j++;
            }
            //converting the character array to string to be able to return as a string
            for(int i=0;i<len;i++){
            answer+=ans[i];
            }
            return answer;
    }
    //if the array is possible
    else if(len%2==0 && odd==0){
            //we create the array by
            char ans[1000];
            string answer;
            int j=0;
        // we are filling the answer string with the numbers from the original string as far as possible by maintaining it as a pallindrome
        for(int i=0;i<len;i++){
                //if the element has not been used then we store it in  the answer array
                if(arr[n[i]-'0']>0){
                ans[j]=n[i];
                ans[len-j-1]=n[i];
                arr[n[i]-'0']=arr[n[i]-'0']-2;
                }
                //incrementing positions for the original string answer array
                j++;
            }
            //converting the character array to string to be able to return as a string
            for(int i=0;i<len;i++){
                answer+=ans[i];
            }
            return answer;
    }
    //if the array is not possible
    else{
    return "NOT POSSIBLE";
    }
}
}
int main(){
    string number;
    cin>>number;

    cout<<smallestPallindromicNumber(number);

    return 0;

}

Complexity

Time complexity: 0(N)
Space complexity: O(1)

where N is the number of digits in the input number.

With this article at OpenGenus, you will have the complete idea of solving this problem. Enjoy.