the palin (http://www.spoj.com/problems/PALIN/) prob on spoj requires to handle no. ranging from 1 to 10^6 in length, thus i need to convert string to bigints, but library method throws an exception which is difficult to understand.
plz help heres my code (http://ideone.com/9N3a9p) with comments explaining the prob…
you donot need an atoi function here , if you use atoi function you will get errors , because atoi function returns an integer but if the string is too large atoi will not work .
so here is an algorithm which will not use atoi at all :-
A careful observation into what a palindrome means gives us a hint to solve the problem. Since a palindrome is effectively “mirrored” around the central digit(s) of a number, we can reflect the first half of the number onto the second half. Keep note that if the number of digits in the number is even - there will be more than one “central” element. So for example, given an input number of say, 1594 - we mirror it to 1551. This number is already a palindrome but obviously it’s smaller than the input number so we need to do further work (if it’s already larger than, this is the next palindrome after K). Now if we have a palindrome that is less than or equal to the intended number we need to have an algorithm that:
Increases the number but maintains it as a palindrome
Ensure that we don’t skip any palindromes on the way
If we take note that a palindrome must be mirrored, then we can deduce that the next largest palindrome would be one with its central most digit incremented. This can be derived from the fact that the next largest (not necessarily palindrome) number is one with its LSD (least significant digit) increased by 1, however since we need to retain it as a palindrome it also means the MSD will need to be increased also - which is far from optimal. You can observe from this that the most optimal strategy would be to increase the center digits due to the mirror-like property of palindromes. From the example above, if we incremented the first (and consequently last) digit then we yield 2552, however this isn’t the most optimal step because you can modify the central digits to 1661 and retain palindrome status.
So we have a basic strategy but it isn’t complete. What happens if the center digits happened to be 9’s? You set the currently operating digits to be 0 and increment the next pair of digits as this yields the next smallest number. For example, given 1999 - you first mirror it to 1991, increment the center digits to yield 1001 and then increment the next set of digits to yield 2002 - which is the expected answer. This obviously needs to be looped via iteration or called recursively for multiple 9’s.
So are we done yet? Not quite. There is still one minor case we need to cover, it’s one that reaches to the MSD but still needs to “carry on” the increments or more simply “all 9’s”. A basic example would be 9999, if you do the algorithm above then you end up yielding 0000 and still need to increment 1 to the next set of digits (which don’t exist as of yet). Covering this case is rather simple, add an extra digit ‘1’ to the beginning of the number (i.e. 0000 -> 10000) and change the LSD to a 1 also (for obvious reasons).
YOU CAN USE STRING FOR ALL THESE FUNCTIONS , no need of atoi ,