Reverse the Digits

Q: How do you reverse the digits of a number without converting it to a string?

Repeat two steps until the number is 0 : take the last digit with n % 10 and append it to the result with result = result * 10 + digit , then drop it with n = n / 10 using integer division. For 1234 the result grows as 4, 43, 432 and 4321.

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. With larger inputs, check result > (INT_MAX - digit) / 10 before each multiplication.

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.

+13 hidden tests on Submit

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 it is a fine first answer. Interviewers usually follow up by asking 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 exactly the characters of its decimal text. Turn n into text, reverse the characters, and read the text back as a number. 1234 becomes "1234", then "4321", then 4321.

The leading zeros take care of themselves. Reversing 120 gives the text "021", and parsing it as a number ignores the zero in front and returns 21.

A number below 10^9 has at most 9 digits, and the work and the extra text both grow with the number of digits, which is O(log n).

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 the digits off the end of n one at a time and add each one to the end of a new number. n % 10 is the last digit of n, and n / 10 with integer division drops it. To add a digit d to the end of result, shift what is there one place left and put d in the ones place: result * 10 + d.

For 1234, result goes 4, 43, 432, 4321 while n goes 123, 12, 1, 0. The loop stops when n reaches 0, so it runs once per digit.

Leading zeros never appear. For 120, the first digit taken is 0, and 0 * 10 + 0 is still 0, so it leaves no trace. 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

Most bugs come from division and from the end of the loop.

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 questions4

How do you reverse the digits of a number without converting it to a string?

Repeat two steps until the number is 0: take the last digit with n % 10 and append it to the result with result = result * 10 + digit, then drop it with n = n / 10 using integer division. For 1234 the result grows as 4, 43, 432 and 4321.

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. With larger inputs, check result > (INT_MAX - digit) / 10 before each multiplication.

Python

def reverseDigits(n):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

n = 1234

Expected