## The challenge

Number is a palindrome if it is equal to the number with digits in reversed order. For example, `5``44``171``4884` are palindromes, and `43``194``4773` are not.

Write a function which takes a positive integer and returns the number of special steps needed to obtain a palindrome. The special step is: “reverse the digits, and add to the original number”. If the resulting number is not a palindrome, repeat the procedure with the sum until the resulting number is a palindrome.

If the input number is already a palindrome, the number of steps is ``.

All inputs are guaranteed to have a final palindrome which does not overflow `long`.

### Example

For example, start with `87`:

 ``````1 2 3 4 `````` `````` 87 + 78 = 165 - step 1, not a palindrome 165 + 561 = 726 - step 2, not a palindrome 726 + 627 = 1353 - step 3, not a palindrome 1353 + 3531 = 4884 - step 4, palindrome! ``````

`4884` is a palindrome and we needed `4` steps to obtain it, so answer for `87` is `4`.

Some interesting information on the problem can be found in this Wikipedia article on Lychrel numbers.

## The solution in Java code

Option 1:

 ``````1 2 3 4 5 6 7 8 `````` ``````public class Palindromes { public static int palindromeChainLength (long n) { String ns = "" + n, nrs = "" + new StringBuilder(ns).reverse(); return ns.equals(nrs) ? 0 : 1 + palindromeChainLength(n + Long.valueOf(nrs)); } } ``````

Option 2:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 `````` ``````public class Palindromes { public static int palindromeChainLength(long n) { int step = 0; while (n != reverseNumber(n)) { n = n + reverseNumber(n); step++; } return step; } private static long reverseNumber(long n) { char[] number = String.valueOf(n).toCharArray(); String reverseNumber = ""; for (int count = number.length - 1; count >= 0; count--) { reverseNumber = reverseNumber + number[count]; } return Long.parseLong(reverseNumber); } } ``````

Option 3:

 ``````1 2 3 4 5 6 7 8 `````` ``````public class Palindromes { public static int palindromeChainLength (long n) { String s = String.valueOf(n); String r = new StringBuilder(String.valueOf(n)).reverse().toString(); if (s.equals(r)) return 0; return 1 + palindromeChainLength(n + Long.parseLong(r)); } } ``````

## Test cases to validate our solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 `````` ``````import org.junit.Test; import static org.junit.Assert.*; public class PalindromesTest { @Test public void testPalindrome() { assertEquals(0, Palindromes.palindromeChainLength(1)); assertEquals(0, Palindromes.palindromeChainLength(88)); assertEquals(0, Palindromes.palindromeChainLength(393)); } @Test public void testNonPalindrome() { assertEquals(1, Palindromes.palindromeChainLength(10)); assertEquals(1, Palindromes.palindromeChainLength(134)); assertEquals(4, Palindromes.palindromeChainLength(87)); assertEquals(7, Palindromes.palindromeChainLength(2897)); assertEquals(24, Palindromes.palindromeChainLength(89)); } } ``````