Skip to content

Instantly share code, notes, and snippets.

@John61590
Created April 25, 2017 08:35
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save John61590/e9efe7a7516906f5010a09a048c65373 to your computer and use it in GitHub Desktop.
Save John61590/e9efe7a7516906f5010a09a048c65373 to your computer and use it in GitHub Desktop.
Find nearest integer palindrome in Java (best algorithm)
public class NearestIntegerPalindrome {
public static int findClosestPalindrome(int x) {
if (x < 0) {
return -1;
}
//special case: 100 -> 99 palindrome is closest
if (x != 1 && isPower10(x)) {
return x - 1;
}
String value = x + "";
int inputLength = value.length();
//first half
String first1 = value.substring(0, ((inputLength + 1) / 2));
int palindrome1 = Integer.parseInt(reflect(first1, inputLength / 2));
//if the "lower" palindrome is found, increase by 1 or if the "higher" palindrome is found, decrease by 1
int twiddleDirection = palindrome1 <= x ? 1 : -1;
String first2 = (Integer.parseInt(first1) + twiddleDirection) + "";
int palindrome2 = Integer.parseInt(reflect(first2, inputLength / 2));
//if palindrome2 has more of a distance than palindrome1, return palindrome1 (smallest)
return Math.abs(x - palindrome1) <= Math.abs(palindrome2 - x) ? palindrome1 : palindrome2;
}
public static String reflect(String left, int n) {
String reverse = new StringBuilder(left.substring(0, n)).reverse().toString();
return left + reverse;
}
public static boolean isPower10(int x) {
while (x > 9 && x % 10 == 0)
x /= 10;
return x == 1;
}
public static void main(String[] args) {
System.out.println(findClosestPalindrome(0));
System.out.println(findClosestPalindrome(1));
System.out.println(findClosestPalindrome(6));
System.out.println(findClosestPalindrome(9));
System.out.println(findClosestPalindrome(10));
System.out.println(findClosestPalindrome(11));
System.out.println(findClosestPalindrome(12));
System.out.println(findClosestPalindrome(71));
System.out.println(findClosestPalindrome(74));
System.out.println(findClosestPalindrome(79));
System.out.println(findClosestPalindrome(99));
System.out.println(findClosestPalindrome(100));
System.out.println(findClosestPalindrome(101));
System.out.println(findClosestPalindrome(999));
System.out.println(findClosestPalindrome(1993));
System.out.println(findClosestPalindrome(1999));
System.out.println(findClosestPalindrome(9900));
System.out.println(findClosestPalindrome(999000));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment