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