Originally the problem said the numbers will be in the range 1 to 2000. I see this has been lowered to 1000 now. I updated my code accordingly.
Use Python 3. Or if you insist on Python 2, use unichr instead of chr.
@sha256pki Actually I don't know how to determine the time complexity on average, I just saw this conclusion on wikipedia....The worst case should be O(n), but I am not sure about the complexity on average.