[BangPypers] SPOJ : PALIN problem ...

Kishor Bhat kishorbhat at gmail.com
Tue Nov 11 18:34:26 CET 2014


Hi Nikhil,

10 ^ 6 is the maximum number of digits, not the maximum number.

In this solution, you're going to start from K and increment by one,
checking at each stage whether ' n == rev(n)', which is a linear
operation.

Ultimately, this solution will be O(n ^ 2).

A better approach might be to modify the input number directly (by
manipulating the digits).

Also, the extra parentheses around the second raw_input() is not
necessary, but causes no errors.

Regards,
Kishor Bhat

On Tue, Nov 11, 2014 at 10:31 PM, Nikhileshkumar Ikhar
<nikhil.ikhar at gmail.com> wrote:
> Hi Kishor,
> 10^6 is upper limit n is not a huge value. Memory footprint won't be high
> because we need to find only next palindrome number. Or if required for
> loop should be replaced with incremental while loop.
>
> Let me know ur thoughts.
>
> Regards,
> Nikhil
> On 11 Nov 2014 22:11, "Kishor Bhat" <kishorbhat at gmail.com> wrote:
>
>> Hi Avinash,
>>
>> I'd like to point out that the problem statement says that the given
>> integer K has at max 10 ^ 6 digits.
>> This does not mean that K is bounded by 10 ^ 6 !
>>
>> Someone else correct me if I'm wrong, but I don't think this approach
>> will hold for such large inputs.
>>
>> Regards,
>> Kishor Bhat
>>
>> On Tue, Nov 11, 2014 at 4:23 PM, Avinash <avinash.s at paladion.net> wrote:
>> > Hi pals,
>> > I need littele help ..
>> > I made a program as per the given discription in the problem
>> > but when I submit it , Spoj is not accepting it .
>> > Can anyone tell me where I am doing wrong !
>> >
>> > here is the problem set:
>> > http://www.spoj.com/problems/PALIN/
>> >
>> >
>> > and here is my solution:
>> > N=int(raw_input())
>> > if N>0:
>> >     for i in range(0,N):
>> >         IN=(raw_input())
>> >         if(int(IN)>=0 and int(IN)<1000000):
>> >
>> >                 while(True):
>> >                     IN=int(IN)+1
>> >                     IN=str(IN)
>> >                     RIN=reversed(IN)
>> >                     if(list(IN)==list(RIN)):
>> >                         print IN
>> >                         break
>> >
>> >
>> > --
>> > _______________________________________________
>> > BangPypers mailing list
>> > BangPypers at python.org
>> > https://mail.python.org/mailman/listinfo/bangpypers
>> _______________________________________________
>> BangPypers mailing list
>> BangPypers at python.org
>> https://mail.python.org/mailman/listinfo/bangpypers
>>
> _______________________________________________
> BangPypers mailing list
> BangPypers at python.org
> https://mail.python.org/mailman/listinfo/bangpypers


More information about the BangPypers mailing list