Reverse the Digits

Q: What is the time complexity of reversing an integer?

The loop runs once per decimal digit, and a number n has about log10(n) + 1 digits, so the time is O(log n) . The arithmetic version uses O(1) extra space; the string version stores the digits as text, which is O(log n) .

Q: Can reversing an integer overflow?

Yes, when the input can be any 32-bit integer: 1000000009 fits, but its reverse 9000000001 does not. Here n is below 10^9 , so the reverse has at most 9 digits and always fits.

BeginnerMath and simulation

+10

You get a non-negative integer n. Return the number you get by writing its decimal digits in reverse order. Zeros that end up in front are dropped, so 120 becomes 21.

Function

reverseDigits(n: integer) → integer

ninteger: the non-negative integer to reverse
Returnsinteger: the digits of n in reverse order, as a number

Constraints

0 ≤ n < 10⁹
The reversed number also fits in a signed 32-bit integer.

Examples

Input: n = 1234
Output: 4321
Explanation: The digits of 1234 are 1, 2, 3 and 4. Read from the end they are 4, 3, 2 and 1, which is 4321.

Input: n = 120
Output: 21
Explanation: Read backwards, 120 gives the digits 0, 2 and 1. A leading zero does not count in a number, so the answer is 21.

Input: n = 0
Output: 0
Explanation: 0 has a single digit, and reversing it gives 0 again.

Follow-up

If n could be any 32-bit integer, its reverse might not fit. How would you detect that before the multiplication overflows?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Reversing the decimal text is one line in most languages and a fine first answer. Interviewers usually then ask for the same result without strings. The arithmetic version rests on two operations: n % 10 reads the last digit and n / 10 (integer division) removes it.

Reverse the decimal text

Intuition

The digits of a number are the characters of its decimal text. Turn n into text, reverse the characters, and parse the result: 1234 becomes "1234", "4321", then 4321. Leading zeros take care of themselves, because parsing "021" gives 21.

The work and the text both grow with the number of digits, O(log n), at most 9 here.

Algorithm

Convert n to its decimal text.
Reverse the characters.
Parse the reversed text as an integer and return it.

def reverseDigits(n):
    # int() ignores the leading zeros that trailing zeros turn into.
    return int(str(n)[::-1])

Pop and push digits with arithmetic

Intuition

Take digits off the end of n and add each one to the end of result: result * 10 + d shifts what is there one place left and puts d in the ones place. For 1234, result goes 4, 43, 432, 4321 while n goes 123, 12, 1, 0. The loop runs once per digit.

Leading zeros never appear: for 120 the first digit taken is 0, and 0 * 10 + 0 is still 0. For n = 0 the loop never runs and the answer is 0. Only two integers are kept, so the extra space is O(1).

Algorithm

Set result = 0.
While n is greater than 0, compute the last digit n % 10.
Set result = result * 10 + digit.
Drop the digit with n = n / 10, using integer division.
Return result.

def reverseDigits(n):
    result = 0
    while n > 0:
        result = result * 10 + n % 10  # push the last digit of n
        n //= 10                        # drop it from n
    return result

Pitfalls and edge cases

Using ordinary division where you need integer division. In JavaScript, Python 3 and Lua, n / 10 gives 123.4, so n never becomes a whole number again and result fills up with fractions. Use Math.floor, // or your language's integer division.
Writing the loop as while n >= 10. It stops before the last digit, so 1234 comes back as 432.
Returning the reversed text without parsing it. "021" is not the number 21, and the comparison with the expected answer fails.
Formatting a double in R with as.character. When n is stored as a double, it prints 100000000 as 1e+08, and the reversed text is 80+e1. Use format(n, scientific = FALSE).

Frequently asked questions3

What happens to trailing zeros when you reverse a number?

They would become leading zeros, which a number does not have, so they disappear. Reversing 120 gives 21, and reversing 100000000 gives 1. The arithmetic loop drops them on its own, because adding 0 to an empty result leaves it at 0.

What is the time complexity of reversing an integer?

The loop runs once per decimal digit, and a number n has about log10(n) + 1 digits, so the time is O(log n). The arithmetic version uses O(1) extra space; the string version stores the digits as text, which is O(log n).

Can reversing an integer overflow?

Yes, when the input can be any 32-bit integer: 1000000009 fits, but its reverse 9000000001 does not. Here n is below 10^9, so the reverse has at most 9 digits and always fits.

def reverseDigits(n):
    # Write code here

Test #1

Test #2

Test #3

Argument

n = 1234

Expected Output