Thursday, May 16, 2013
Next Palindrome
Given any number up to 1000000 digits long (far too large for any int double long float or any other number format common to programming languages) find the next lowest palindrome. So for example, if the number is 5, the next lowest is 6, given 9 the next lowest is 11, given 12 the next lowest is 22, given 123123 the next lowest is 123321, and the final example given 9877899835481354687 the next lowest would be 9877899836389987789. If the current number is a palindrome, find the next lowest after the current number.
Subscribe to:
Post Comments (Atom)
I'll explain my solution, and then post it below. After much headbanging against walls I recognized a pattern. The second half is always either the reverse of the first half, or the reverse of the first half incremented by 1. In comment form, my code turned into this
ReplyDelete//read in line
//increment line by 1
//if first half is greater than second half
// return firsthalf + middle + reveresedfirsthalf
//else
// if even length number
// return incrementedfirsthalf + reversedincrementedfirsthalf
// else
// if middle == 9
// return incrementedfirsthalf + middle + reversedincrementedfirsthalf
// else
// return firsthalf + incrementedmiddle + reversedfirsthalf
that last part of incrementing the middle, or the first half was a little troublesome. I realized I'm not always dealing with even length numbers, so I just took that middle digit out, and stored it elsewhere, unless it's of even length, then i stored it as "", which is nothing.
ugh... i hate not keeping the line spacing. Everything after that first else, is inside that else statement. I should've done brackets. -_-
Deletemy code:
ReplyDelete// finds the next palindrome and returns it in char[] format
private static char[] nextPalin(String string) {
int length = string.length();
int curNum = Character.getNumericValue(string.charAt(length - 1));
char[] newString = string.toCharArray();
if (length == 1 && curNum < 9) {
String num = "" + (curNum + 1);
newString[0] = num.charAt(0);
return newString;
}
newString = increment(string, newString);
return palinize(new String(newString));
}
// increments the number... a little hard than i initially thought.
private static char[] increment(String string, char[] newString) {
int index = string.length() - 1;
int curNum = Character.getNumericValue(string.charAt(index));
boolean changed = true;
while (changed) {
changed = false;
if (curNum == 9) {
newString[index] = '0';
changed = true;
if (index != 0) {
curNum = Character.getNumericValue(string.charAt(--index));
} else {
changed = false;
char[] temp = new char[newString.length + 1];
temp[0] = '1';
for (int i = 0; i < newString.length; i++)
temp[i + 1] = newString[i];
newString = temp;
}
} else
newString[index] = Integer.toString(curNum + 1).charAt(0);
}
return newString;
}
// turns the number into the next lowest palindrome
private static char[] palinize(String newString) {
int length = newString.length();
int half = length / 2;
String first = newString.substring(0, half);
String reversed = new StringBuffer(first).reverse().toString();
String second = "";
String third;
if (length % 2 == 1) {
second = newString.substring(half, half + 1);
third = newString.substring(half + 1, length);
} else
third = newString.substring(half, length);
String response;
if (greaterThan(reversed, third)) {
response = first + second + reversed;
return response.toCharArray();
} else {
if (second.equals("")) {
char[] one = first.toCharArray();
one = increment(first, one);
first = new String(one);
reversed = new StringBuffer(first).reverse().toString();
response = first + second + reversed;
return response.toCharArray();
} else {
if (Integer.parseInt(second) == 9) {
second = "0";
char[] one = first.toCharArray();
one = increment(first, one);
first = new String(one);
reversed = new StringBuffer(first).reverse().toString();
response = first + second + reversed;
return response.toCharArray();
} else {
char[] two = second.toCharArray();
two = increment(second, two);
second = new String(two);
response = first + second + reversed;
return response.toCharArray();
}
}
}
}
// compares the numeric values of the strings, same as >=
private static boolean greaterThan(String reversed, String third) {
char[] rev = reversed.toCharArray();
char[] thi = third.toCharArray();
for (int i = 0; i < rev.length; i++) {
int first = Character.getNumericValue(rev[i]);
int second = Character.getNumericValue(thi[i]);
if (first < second)
return false;
else if (first > second)
return true;
}
return true;
}