A better algorithm to find the next palindrome of a number string

Question

Firstly here is the problem:

A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

Input: The first line contains integer t, the number of test cases. Integers K are given in the next t lines.

Output: For each K, output the smallest palindrome larger than K. Example

Input:

2

808

2133

Output:

818

2222

Secondly here is my code:

// I know it is bad practice to not cater for erroneous input,
// however for the purpose of the execise it is omitted
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.lang.Exception;
import java.math.BigInteger;

public class Main
{    
    public static void main(String [] args){   
        try{
            Main instance = new Main(); // create an instance to access non-static
                                        // variables
        
            // Use java.util.Scanner to scan the get the input and initialise the
            // variable
            Scanner sc=null;

            BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

            String input = "";

            int numberOfTests = 0;

            String k; // declare any other variables here
            
            if((input = r.readLine()) != null){
                sc = new Scanner(input);
                numberOfTests = sc.nextInt();
            }

            for (int i = 0; i < numberOfTests; i++){
                if((input = r.readLine()) != null){
                    sc = new Scanner(input);
                    k=sc.next(); // initialise the remainder of the variables sc.next()
                    instance.palindrome(k);
                } //if
            }// for
        }// try

        catch (Exception e)
        {
            e.printStackTrace();
        }
    }// main

    public void palindrome(String number){

        StringBuffer theNumber = new StringBuffer(number);
        int length = theNumber.length();
        int left, right, leftPos, rightPos;
        // if incresing a value to more than 9 the value to left (offset) need incrementing
        int offset, offsetPos;
        boolean offsetUpdated;
        // To update the string with new values
        String insert;
        boolean hasAltered = false;

        for(int i = 0; i < length/2; i++){
            leftPos = i; 
            rightPos = (length-1) - i;
            offsetPos = rightPos -1; offsetUpdated = false;
            
            // set values at opposite indices and offset
            left = Integer.parseInt(String.valueOf(theNumber.charAt(leftPos)));
            right = Integer.parseInt(String.valueOf(theNumber.charAt(rightPos)));
            offset = Integer.parseInt(String.valueOf(theNumber.charAt(offsetPos)));

            if(left != right){
                // if r > l then offest needs updating
                if(right > left){
                    // update and replace
                    right = left;
                    insert = Integer.toString(right);

                    theNumber.replace(rightPos, rightPos + 1, insert);
                
                    offset++; if (offset == 10) offset = 0;
                    insert = Integer.toString(offset);

                    theNumber.replace(offsetPos, offsetPos + 1, insert);
                    offsetUpdated = true;
               
                    // then we need to update the value to left again
                    while (offset == 0 && offsetUpdated){ 
                        offsetPos--;
                        offset =
                            Integer.parseInt(String.valueOf(theNumber.charAt(offsetPos)));
                        offset++; if (offset == 10) offset = 0;
                        // replace
                        insert = Integer.toString(offset);
                        theNumber.replace(offsetPos, offsetPos + 1, insert);
                    }
                    // finally incase right and offset are the two middle values
                    left = Integer.parseInt(String.valueOf(theNumber.charAt(leftPos)));
                    if (right != left){
                        right = left;
                        insert = Integer.toString(right);
                        theNumber.replace(rightPos, rightPos + 1, insert);
                    }
                }// if r > l
                else
                    // update and replace
                    right = left;
                    insert = Integer.toString(right);
                    theNumber.replace(rightPos, rightPos + 1, insert);           
            }// if l != r
        }// for i
        System.out.println(theNumber.toString());
    }// palindrome
}

Finally my explaination and question.

My code compares either end and then moves in
    if left and right are not equal
        if right is greater than left
            (increasing right past 9 should increase the digit
             to its left i.e 09 ---- > 10) and continue to do
             so if require as for 89999, increasing the right
             most 9 makes the value 90000
        
             before updating my string we check that the right
             and left are equal, because in the middle e.g 78849887
             we set the 9 --> 4 and increase 4 --> 5, so we must cater for this.

The problem is from spoj.pl an online judge system. My code works for all the test can provide but when I submit it, I get a time limit exceeded error and my answer is not accepted.

Does anyone have any suggestions as to how I can improve my algorithm. While writing this question i thought that instead of my while (offset == 0 && offsetUpdated) loop i could use a boolean to to make sure i increment the offset on my next [i] iteration. Confirmation of my chang or any suggestion would be appreciated, also let me know if i need to make my question clearer.

Answer 1

This seems like a lot of code. Have you tried a very naive approach yet? Checking whether something is a palindrome is actually very simple.

private boolean isPalindrome(int possiblePalindrome) {
    String stringRepresentation = String.valueOf(possiblePalindrome);
    if ( stringRepresentation.equals(stringRepresentation.reverse()) ) {
       return true;
    }
}

Now that might not be the most performant code, but it gives you a really simple starting point:

private int nextLargestPalindrome(int fromNumber) {
    for ( int i = fromNumber + 1; ; i++ ) {
        if ( isPalindrome( i ) ) {
            return i;
        }
    }
}

Now if that isn't fast enough you can use it as a reference implementation and work on decreasing the algorithmic complexity.

There should actually be a constant-time (well it is linear on the number of digits of the input) way to find the next largest palindrome. I will give an algorithm that assumes the number is an even number of digits long (but can be extended to an odd number of digits).

1. Find the decimal representation of the input number ("2133").
2. Split it into the left half and right half ("21", "33");
3. Compare the last digit in the left half and the first digit in the right half.
   a. If the right is greater than the left, increment the left and stop. ("22")
   b. If the right is less than the left, stop.
   c. If the right is equal to the left, repeat step 3 with the second-last digit in the left and the second digit in the right (and so on).
4. Take the left half and append the left half reversed. That's your next largest palindrome. ("2222")

Applied to a more complicated number:

1.    1234567887654322
2.    12345678   87654322
3.    12345678   87654322
             ^   ^         equal
3.    12345678   87654322
            ^     ^        equal
3.    12345678   87654322
           ^       ^       equal
3.    12345678   87654322
          ^         ^      equal
3.    12345678   87654322
         ^           ^     equal
3.    12345678   87654322
        ^             ^    equal
3.    12345678   87654322
       ^               ^   equal
3.    12345678   87654322
      ^                 ^  greater than, so increment the left

3.    12345679

4.    1234567997654321  answer

This seems a bit similar to the algorithm you described, but it starts at the inner digits and moves to the outer.

Answer 2

There is no reason to fiddle with individual digits when the only needed operation is one simple addition. The following code is based on Raks' answer.

The code stresses simplicity over execution speed, intentionally.

import static org.junit.Assert.assertEquals;

import java.math.BigInteger;
import org.junit.Test;

public class NextPalindromeTest {

    public static String nextPalindrome(String num) {
        int len = num.length();
        String left = num.substring(0, len / 2);
        String middle = num.substring(len / 2, len - len / 2);
        String right = num.substring(len - len / 2);

        if (right.compareTo(reverse(left)) < 0)
            return left + middle + reverse(left);

        String next = new BigInteger(left + middle).add(BigInteger.ONE).toString();
        return next.substring(0, left.length() + middle.length())
             + reverse(next).substring(middle.length());
    }

    private static String reverse(String s) {
        return new StringBuilder(s).reverse().toString();
    }

    @Test
    public void testNextPalindrome() {
        assertEquals("5", nextPalindrome("4"));
        assertEquals("11", nextPalindrome("9"));
        assertEquals("22", nextPalindrome("15"));
        assertEquals("101", nextPalindrome("99"));
        assertEquals("151", nextPalindrome("149"));
        assertEquals("123454321", nextPalindrome("123450000"));
        assertEquals("123464321", nextPalindrome("123454322"));
    }
}

Answer 3

Well I have constant order solution(atleast of order k, where k is number of digits in the number)

Lets take some examples suppose n=17208

divide the number into two parts from middle and reversibly write the most significant part onto the less significant one. ie, 17271 if the so generated number is greater than your n it is your palindrome, if not just increase the center number(pivot) ie, you get 17371

other examples

n=17286 palidrome-attempt=17271(since it is less than n increment the pivot, 2 in this case) so palidrome=17371

n=5684 palidrome1=5665 palidrome=5775

n=458322 palindrome=458854

now suppose n = 1219901 palidrome1=1219121 incrementing the pivot makes my number smaller here so increment the number adjacent pivot too 1220221

and this logic could be extended

Answer 4

public class NextPalindrome 
{   
    int rev, temp;
    int printNextPalindrome(int n) 
    {
        int num = n;
        for (int i = num+1; i >= num; i++) 
        {
            temp = i;
            rev = 0;
            while (temp != 0) 
            {
                int remainder = temp % 10;
                rev = rev * 10 + remainder;
                temp = temp / 10;
            }
            if (rev == i) 
            {
                break;
            }
        }
        return rev;
    }
    public static void main(String args[]) 
    {
        NextPalindrome np = new NextPalindrome();
        int nxtpalin = np.printNextPalindrome(11);
        System.out.println(nxtpalin);
    }



}

Answer 5

Here is my code in java. Whole idea is from here.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("Enter number of tests: ");
        int t = sc.nextInt();

        for (int i = 0; i < t; i++) {
            System.out.println("Enter number: ");
            String numberToProcess = sc.next(); // ne proveravam dal su brojevi
            nextSmallestPalindrom(numberToProcess);
        }
    }

    private static void nextSmallestPalindrom(String numberToProcess) {
        

        int i, j;

        int length = numberToProcess.length();
        int[] numberAsIntArray = new int[length];
        for (int k = 0; k < length; k++)
            numberAsIntArray[k] = Integer.parseInt(String
                    .valueOf(numberToProcess.charAt(k)));

        numberToProcess = null;

        boolean all9 = true;
        for (int k = 0; k < length; k++) {
            if (numberAsIntArray[k] != 9) {
                all9 = false;
                break;
            }
        }
        // case 1, sve 9ke
        if (all9) {
            whenAll9(length);
            return;
        }

        int mid = length / 2;
        if (length % 2 == 0) {
            i = mid - 1;
            j = mid;
        } else {
            i = mid - 1;
            j = mid + 1;
        }
        
        while (i >= 0 && numberAsIntArray[i] == numberAsIntArray[j]) {
            i--;
            j++;
        }
        // case 2 already polindrom
        if (i == -1) {
            if (length % 2 == 0) {
                i = mid - 1;
                j = mid;
            } else {
                i = mid;
                j = i;
            }
            addOneToMiddleWithCarry(numberAsIntArray, i, j, true);

        } else {
            // case 3 not polindrom
            if (numberAsIntArray[i] > numberAsIntArray[j]) { // 3.1)
                
                while (i >= 0) {
                    numberAsIntArray[j] = numberAsIntArray[i];
                    i--;
                    j++;
                }
                for (int k = 0; k < numberAsIntArray.length; k++)
                    System.out.print(numberAsIntArray[k]);
                System.out.println();
            } else { // 3.2 like case 2
                if (length % 2 == 0) {
                    i = mid - 1;
                    j = mid;
                } else {
                    i = mid;
                    j = i;
                }
                addOneToMiddleWithCarry(numberAsIntArray, i, j, false);
            }
        }
    }

    private static void whenAll9(int length) {
        
        for (int i = 0; i <= length; i++) {
            if (i == 0 || i == length)
                System.out.print('1');
            else
                System.out.print('0');
        }
    }

    private static void addOneToMiddleWithCarry(int[] numberAsIntArray, int i,
            int j, boolean palindrom) {
        numberAsIntArray[i]++;
        numberAsIntArray[j] = numberAsIntArray[i];
        while (numberAsIntArray[i] == 10) {
            numberAsIntArray[i] = 0;
            numberAsIntArray[j] = numberAsIntArray[i];
            i--;
            j++;
            numberAsIntArray[i]++;
            numberAsIntArray[j] = numberAsIntArray[i];
        }
        
        if (!palindrom)
            while (i >= 0) {
                numberAsIntArray[j] = numberAsIntArray[i];
                i--;
                j++;
            }
        
        for (int k = 0; k < numberAsIntArray.length; k++)
            System.out.print(numberAsIntArray[k]);
        System.out.println();
    }

}