5
\$\begingroup\$

I'm practicing some python exercise and I have some doubts about the solution of reversing a number. Example, 42 -> 24, -314 -> -413.

The book has this solution:

def reverse(x: int) -> int:
  result, x_remaining = 0, abs(x)
  while x_remaining:
      result = result * 10 + x_remaining % 10
      x_remaining //= 10
  return -result if x < 0 else result

My solution:

def reverse_digit(x: int) -> int:
  s = str(abs(x))
  result = s[::-1]
  if x >= 0:
    return int(result)
  else:
    return int("-" + result)

The book says that converting the number to string would be a brute-force solution but don't they have the same time complexity, O(n)?

Is the book solution that much better than mine (that in my opinion is much simpler and easy to read)?

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Since Code Review is a community where programmers improve their skills through peer review, we require that the code be posted by an author or maintainer of the code, that the code be embedded directly, and that the poster know why the code is written the way it is. We can not review code that's in a book, there are legal, moral and practical reasons for that. Please take a look at the help center. \$\endgroup\$
    – Mast
    Oct 19, 2020 at 11:11
  • 7
    \$\begingroup\$ @Mast I interpret this differently. The OP has their own code; understands their own code; and wants to know if it's better-structured than the reference implementation. The verbiage might be strengthened to indicate that, but I don't consider this off-topic. \$\endgroup\$
    – Reinderien
    Oct 19, 2020 at 13:39
  • 2
    \$\begingroup\$ What do you mean with "n" in O(n)? If you mean the number of digits, then neither is O(n). \$\endgroup\$ Oct 19, 2020 at 13:44
  • \$\begingroup\$ @saralance does the book contain any clauses (perhaps in the beginning) that limit its contents from being copied, re-distributed, etc.? relevant meta (see comments) \$\endgroup\$ Oct 19, 2020 at 17:33
  • \$\begingroup\$ @SᴀᴍOnᴇᴌᴀ I'm not a lawyer, but I think 1) such a clause is not even necessary due to default copyright and 2) neither such a clause nor default copyright prevent this from being fair use. \$\endgroup\$ Oct 19, 2020 at 18:10

2 Answers 2

3
\$\begingroup\$

First, a note on complexity. Both your implementation and the reference implementation do indeed have O(n) complexity in the number of input digits in the best case, but O(log(n)) in the range of the input number.

This depends, mind you, on the expected range of the input number. For "typical values" below the limit of machine precision, which these days will be \$2^{63}\$ for most people, the contents of the reference implementation's inner loop will be constant-time. However, Python has automatic support for arbitrary precision, and if that support is used, the reference implementation will end up being super-linear in the worst case.

As for reversal of a negative number, I think it makes less sense to automatically abs() than just to raise, because - if you interpret the number as a string - negative numbers are non-reversible. I say this knowing that it violates the reference implementation if you interpret it as a specification, but I don't think the specification makes much sense.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ First point is not true, second point goes against what's given by the book. \$\endgroup\$ Oct 19, 2020 at 13:50
  • 1
    \$\begingroup\$ @superbrain Why? Are you worried that division and modulation have non-constant time? This may be true in the worst case where the integer exceeds the precision of the machine and invokes Python's built-in arbitrary-precision machinery, but not in the best case. \$\endgroup\$
    – Reinderien
    Oct 19, 2020 at 13:52
  • 1
    \$\begingroup\$ Yes, they're not constant time. And your answer doesn't say best-case and best-case is not particularly interesting. And if you argue with a (not actually given) limit like that, both solutions are not just O(n) but O(1). \$\endgroup\$ Oct 19, 2020 at 13:55
  • 1
    \$\begingroup\$ @superbrain Well, I added some colour for both points. \$\endgroup\$
    – Reinderien
    Oct 19, 2020 at 13:59
  • 1
    \$\begingroup\$ Seems you forgot the general complexity of the OP's solution. \$\endgroup\$ Oct 19, 2020 at 14:06
0
\$\begingroup\$

You could use this function which reverses a string (It's quite similar to your solution but a bit more compact):

def Reverse(Number):
    if Number > 0:
        return int(str(Number)[::-1])
    else:
        Number = str(abs(Number))
        return int("-" + Number[::-1])

Afterthoughts: I did a time test against both of your methods and mine and using this code: https://i.stack.imgur.com/AiHou.png with the last bit calculating the mean of the timings

I got these results:

0.07816539287567138 #Book method
0.10093494892120361 #Your method
0.09026199817657471 #My method
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.