0

I'm pretty new to programming and after learning the basics, I tried doing some SPOJ problems. Turns out most of my programs are inefficient and time out even though they are correct (I think)

For example, the following program takes n as number of test cases and prints the next largest palindrome.

n = int(raw_input())
a=[0]*n
for i in range (0,n):
  a[i]=int(raw_input())
for i in range (0,n):
   var=a[i]+1
   flag=False
   varstr=str(var)
   while flag==False:
    if varstr==(varstr[::-1]):
      flag=True
      print var
      break
    else:
      var+=1;

I'm getting the right outputs, but the time is always the problem.

How do I make my code more efficient? Is there something I'm missing?

Chris Martin
  • 30,334
  • 10
  • 78
  • 137
Master_Pabu
  • 23
  • 1
  • 4
  • I used this problem only as an example. Same problem yes but in my case I'm getting the right outputs. Also I'm having the problem of inefficiency on several of my solutions. – Master_Pabu Jul 19 '15 at 08:50
  • if the input is 22322, what is the next palindrome, 33433? – omri_saadon Jul 19 '15 at 08:51
  • 1
    The next would be 22422 – Master_Pabu Jul 19 '15 at 08:54
  • 1
    many SPOJ-Problems have a brute-force solution, that takes to long. So if your solution is O(N^2) and there is for example a O(N * log N) solution, in the test data N is so large, that O(N^2) would take ages (minutes). – Daniel Jul 19 '15 at 08:56
  • @omri_saadon: The answer by Andrew Callahan in the link you posted is quite efficient. And probably deserves an upvote or two... – PM 2Ring Jul 19 '15 at 08:57
  • What Daniel said. The way to get better is to do lots of problems like this so that you learn about those more efficient algorithms & learn to recognize when they fit the situation at hand. But really, this question is a bit too broad for SO. – PM 2Ring Jul 19 '15 at 09:03
  • Ok, thanks. I saw Andrew Callahan's solution, and I never thought of just generating the next number without actually brute-forcing through every number consecutively. Also, I'm very very new to SO. Where do you suggest I get help on problems like this? – Master_Pabu Jul 19 '15 at 09:10
  • Two suggestions: Upgrade to Python 3 and use `xrange()` instead of `range()`. Also, check out PEP 8 and remove `flag`, which is effectively unused. – Ulrich Eckhardt Jul 19 '15 at 09:12
  • @Master_Pabu: [Code Review](http://codereview.stackexchange.com/) can help you with making your code more efficient (but read their rules before posting code). To get better at programming (apart from just doing lots of practice problems) read code written by good programmers. And maybe join a programmer's discussion forum, eg [xkcd Coding](http://forums.xkcd.com/viewforum.php?f=11). – PM 2Ring Jul 19 '15 at 09:29

0 Answers0