Mead3000 - 1 year ago 50

Java 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 Source

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).

- Find the decimal representation of the input number ("2133").
- Split it into the left half and right half ("21", "33");
- 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). - 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.