[BangPypers] SPOJ : PALIN problem ...

Nikhileshkumar Ikhar nikhil.ikhar at gmail.com
Wed Nov 12 05:48:26 CET 2014


my bad. I'm wrong at many levels.
Yes you are correct, for very large input it will be O(n^2).

Regards,
Nikhil


On 11 November 2014 23:04, Kishor Bhat <kishorbhat at gmail.com> wrote:

> 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
> _______________________________________________
> BangPypers mailing list
> BangPypers at python.org
> https://mail.python.org/mailman/listinfo/bangpypers
>


More information about the BangPypers mailing list