Given a number, find the next smallest palindrome | GeeksforGeeks

Given a number, find the next smallest palindrome | GeeksforGeeks
Given a number, find the next smallest palindrome larger than this number. For example, if the input number is "2 3 5 4 5″, the output should be "2 3 6 3 2″. And if the input number is "9 9 9″, the output should be "1 0 0 1″.

Step 1. Initially, ignore the part of left side which is same as the corresponding part of right side. For example, if the number is “8 3 4 2 2 4 6 9″, we ignore the middle four elements. i now points to element 3 and j now points to element 6.

Step 2. After step 1, following cases arise:

Case 1: Indices i & j cross the boundary.
This case occurs when the input number is palindrome. In this case, we just add 1 to the middle digit (or digits in case n is even) propagate the carry towards MSB digit of left side and simultaneously copy mirror of the left side to the right side.
For example, if the given number is “1 2 9 2 1″, we increment 9 to 10 and propagate the carry. So the number becomes “1 3 0 3 1″

Case 2: There are digits left between left side and right side which are not same. So, we just mirror the left side to the right side & try to minimize the number formed to guarantee the next smallest palindrome.
In this case, there can be two sub-cases.

2.1) Copying the left side to the right side is sufficient, we don’t need to increment any digits and the result is just mirror of left side. Following are some examples of this sub-case.
Next palindrome for “7 8 3 3 2 2″ is “7 8 3 3 8 7″
Next palindrome for “1 2 5 3 2 2″ is “1 2 5 5 2 1″
Next palindrome for “1 4 5 8 7 6 7 8 3 2 2″ is “1 4 5 8 7 6 7 8 5 4 1″
How do we check for this sub-case? All we need to check is the digit just after the ignored part in step 1. This digit is highlighted in above examples. If this digit is greater than the corresponding digit in right side digit, then copying the left side to the right side is sufficient and we don’t need to do anything else.

2.2) Copying the left side to the right side is NOT sufficient. This happens when the above defined digit of left side is smaller. Following are some examples of this case.
Next palindrome for “7 1 3 3 2 2″ is “7 1 4 4 1 7″
Next palindrome for “1 2 3 4 6 2 8″ is “1 2 3 5 3 2 1″
Next palindrome for “9 4 1 8 7 9 7 8 3 2 2″ is “9 4 1 8 8 0 8 8 1 4 9″
We handle this subcase like Case 1. We just add 1 to the middle digit (or digits in ase n is even) propagate the carry towards MSB digit of left side and simultaneously copy mirror of the left side to the right side.

    static void generateNextPalindromeUtil(int num[], int n)

    {

        int mid = n / 2;

 

        // end of left side is always 'mid -1'

        int i = mid - 1;

         

        // Begining of right side depends

        // if n is odd or even

        int j = (n % 2 == 0) ? mid : mid + 1;

         

        // A bool variable to check if copy of left

        // side to right

        // is sufficient or not

        boolean leftsmaller = false;

 

        // Initially, ignore the middle same digits

        while (i >= 0 && num[i] == num[j])

        {

            i--;

            j++;

        }

         

        // Find if the middle digit(s) need to

        // be incremented or not (or copying left

        // side is not sufficient)

        if (i < 0 || num[i] < num[j])

        {

            leftsmaller = true;

        }

         

        // Copy the mirror of left to tight

        while (i >= 0)

        {

            num[j++] = num[i--];

        }

         

        // Handle the case where middle digit(s)

        // must be incremented. This part of code

        // is for CASE 1 and CASE 2.2

        if (leftsmaller)

        {

            int carry = 1;

         

            // If there are odd digits, then increment

            // the middle digit and store the carry

            if (n % 2 == 1) {

                num[mid] += 1;

                carry = num[mid] / 10;

                num[mid] %= 10;

            }

            i = mid - 1;

            j = (n % 2 == 0 ? mid : mid + 1);

             

            // Add 1 to the rightmost digit of the left

            // side, propagate the carry towards MSB digit

            // and simultaneously copying mirror of the

            // left side to the right side.

            while (i >= 0)

            {

                num[i] = num[i] + carry;

                carry = num[i] / 10;

                num[i] %= 10;

                num[j] = num[i];// copy mirror to right

                i--;

                j++;

            }

 

        }

    }

 

    // The function that prints next palindrome

    // of a given number num[] with n digits.

    static void generateNextPalindrome(int num[], int n)

    {

        System.out.println("Next Palindrome is:");

         

        // Input type 1: All the digits are 9,

        // simply o/p 1 followed by n-1 0's

        // followed by 1.

        if (isAll9(num, n)) {

            System.out.print("1");

            for (int i = 0; i < n - 1; i++)

                System.out.print("0");

            System.out.println("1");

 

        }

     

        // Input type 2 and 3

        else {

            generateNextPalindromeUtil(num, n);

            printarray(num);

        }

    }

 

    // A utility function to check if num has all 9s

    static boolean isAll9(int num[], int n) {

        for (int i = 0; i < n; i++)

            if (num[i] != 9)

                return false;

        return true;

    }

http://www.ardendertat.com/2011/12/01/programming-interview-questions-19-find-next-palindrome-number/
http://n1b-algo.blogspot.com/2013/12/palindrome-numbers.html
Read full article from Given a number, find the next smallest palindrome | GeeksforGeeks