Problem Link: http://www.spoj.com/problems/PALIN/

Problem is about finding the next palindrome. Though it sounds simple, it took quite a number of submissions, by ignoring some use cases. I will try to explain how I solved this problem.

1)First of all the input can be large, so I converted the input into int[]
2)check if all the integers in the array are nine,if yes, then make first and last elements of the array as one and rest of them are zero(Note: we must handle the case of single 9)
3)If one of the element of the array is not nine, then initialize two variables i and j pointing to middle element(s) of the array.
4)Decrement i and increment j until i!=j
4.1)if i and j crosses the boundaries of the array, then the number given is palindrome, so add one to the middle element(s) of the array and carry out the extra values after adding 1 to left element and then take the mirror image of the left side to right side.
4.2)else if arr[i] > arr[j] then just take mirror image of left side of the array.
4.3)else if arr[i] < arr[j] then add one to middle element and pass the carry value to the left side. Then take mirror image.

Note: Take care of even numbered palindromes like 11,22,1111

Solution Link: https://github.com/bharaththiruveedula/Algorithms/blob/master/SPOJ/PALIN.java

Advertisements