1 / 6
Sep 2005

in the problem PALIN to search for palindromes it says the input may not contain more than 1000000 digits. but it is impossible to store a number with more than 10 digits . how do i accept such a huge number and search for the palindrome greater than that ?????

    • created

      Sep '05
    • last reply

      Sep '05
    • 5

      replies

    • 263

      views

    • 4

      users

    It's only impossible if you store the number in an int/long. There are no problems if you use e.g. strings.

    if you store the number as a string how do you make calculations like addition , subtraction etc ?????.

    You should not try to add 1 to the number until it becomes a palindrom, that is just incredibly slow. In order to fit in the time limit, you need a smarter algorithm here to directly construct the next palindrom in linear time.

    I don't need addition/subtraction. My solution uses string operations and increment. Fortunately, string increment is a built-in operation in Perl. smile

    Well this is how you can do it. You really don't need string additions( a string +1 is required) . Any way it is better to implement and keep it in your shelf as it may be useful for other problems.

    For 808 => it already a palindrome , then next biggest is 818 , increment the middle one.

    2133 => it isn't a palindrome => take the n/2 digits make it a palindrome=> 2112 => now it is less than given number => increment the n/2th digit 22 => 2222 is the new palindrome.

    2999 => it isn't a palindrome => 29 92 is the number formed =>now add 1 =>30=>3003 is a plaindrome.

    Just manipulate the indexes correctly and perform the addition correctly and modify the method a bit you will get the answer hopefully. It would be easier to visualize and convince yourself and coding would be very easy afterwards.

    Suggested Topics

    Topic Category Replies Views Activity
    C and C++ 0 14 6d

    Want to read more? Browse other topics in C and C++ or view latest topics.