Reverse Integer

The problem

You are given a whole number x from -2,147,483,648 through 2,147,483,647, the range of a signed 32-bit integer. Return the number whose digits are the digits of x in reverse order. A negative number stays negative. Zeros that end up in front are dropped, so 120 becomes 21. If the reversed number falls outside that same range, return 0.

What to write

function solve(x: number): number

Input
x = 123

Output
321

Input
x = -123

Output
-321

Constraints

Preserve the sign.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   x has at most 10 digits, so speed is not the problem. The limit that matters is the range. A reversed number can be much larger than the original: 1,534,236,469 is inside the range, but its reverse, 9,646,324,351, is not, so the answer for it is 0.

2. Hint 2: Ask a smaller question

   Take 123. With arithmetic alone, how do you get its last digit, 3? How do you get what remains, 12? And if you already hold 3 and the next digit is 2, how do you make 32 out of them?

3. Hint 3: Name the pattern

   The remainder after dividing by 10 is the last digit. Dividing by 10 and rounding down removes that digit. Multiplying the answer by 10 and adding a digit puts that digit at the end of the answer. Taking a number apart and building another this way is digit-by-digit arithmetic. The signal: the task is about a number's digits. Read the lesson on digit-by-digit arithmetic.

4. Hint 4: State the invariant

   The answer always holds the digits you have removed so far, in the order you removed them, which is last digit first. The number left holds the digits you have not moved yet. When no digit is left, the answer is the whole reverse.

5. Hint 5: Sketch the pseudocode

   n = x without its sign, answer = 0. While n is not 0: answer = answer × 10 + (remainder of n divided by 10), then n = n divided by 10, rounded down. If x is negative, make answer negative. Return answer if it is inside the range, otherwise 0.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Extract digits with remainder and append them to the result. Check the final signed result against 32-bit bounds; JavaScript can hold the intermediate reversed value exactly.

The slow way

Turn the number into text, reverse the characters and turn the text back into a number. The digits come out right, but a minus sign ends up at the back: -123 becomes "321-", which is not a number. You must take the sign off first, put it back afterward and still check the range. Arithmetic on the number does the same job without any text.

The insight

The last digit of a number is the remainder after dividing by 10, and dividing by 10 and rounding down removes that digit. So the digits come off in the order the reversed number needs them: last digit first. Multiplying the answer by 10 makes room at its end, and adding the digit fills that room.

Step by step

1. Take the sign off the number and start the answer at 0. The loop removes digits by dividing by 10 and rounding down. That only works on a number without a sign: -1 divided by 10, rounded down, is -1 again. So the sign is put back at the end.
2. Repeat while the number still has a digit. Each round moves one digit from the number to the answer. When the number reaches 0, every digit has been moved. For an x of 0 the loop never runs and the answer stays 0.
3. Put the number's last digit at the end of the answer. The remainder after dividing by 10, written % 10, is the last digit. Multiplying the answer by 10 shifts its digits one place left and leaves a 0 at the end, where the new digit goes.
4. Remove that digit from the number. Dividing by 10 and rounding down drops the last digit: 123 becomes 12. JavaScript needs Math.floor for the rounding, because its division gives 12.3. Python's // rounds down by itself.
5. Give the answer the sign of x. The digits were reversed without the sign, so the answer is positive or 0 at this point. A negative x must give a negative result: 321 becomes -321.
6. Return the answer if it is inside the 32-bit range, otherwise 0. The reverse of a 10-digit number can be too large: 1,534,236,469 turns into 9,646,324,351. JavaScript and Python both hold a number of that size exactly, so one check at the end is enough.

The same numbered steps are the comments in each solution.

function solve(x) {
  // 1. Take the sign off the number and start the answer at 0
  let n = Math.abs(x),
    out = 0;
  // 2. Repeat while the number still has a digit
  while (n) {
    // 3. Put the number's last digit at the end of the answer
    out = out * 10 + (n % 10);
    // 4. Remove that digit from the number
    n = Math.floor(n / 10);
  }
  // 5. Give the answer the sign of x
  out = x < 0 ? -out : out;
  // 6. Return the answer if it is inside the 32-bit range, otherwise 0
  return out < -2147483648 || out > 2147483647 ? 0 : out;
}

function solve(x: number): number {
  // 1. Take the sign off the number and start the answer at 0
  let n = Math.abs(x),
    out = 0;
  // 2. Repeat while the number still has a digit
  while (n) {
    // 3. Put the number's last digit at the end of the answer
    out = out * 10 + (n % 10);
    // 4. Remove that digit from the number
    n = Math.floor(n / 10);
  }
  // 5. Give the answer the sign of x
  out = x < 0 ? -out : out;
  // 6. Return the answer if it is inside the 32-bit range, otherwise 0
  return out < -2147483648 || out > 2147483647 ? 0 : out;
}

def solve(x):
    # 1. Take the sign off the number and start the answer at 0
    n = abs(x)
    out = 0
    # 2. Repeat while the number still has a digit
    while n:
        # 3. Put the number's last digit at the end of the answer
        out = out * 10 + n % 10
        # 4. Remove that digit from the number
        n //= 10
    # 5. Give the answer the sign of x
    if x < 0:
        out = -out
    # 6. Return the answer if it is inside the 32-bit range, otherwise 0
    return out if -2147483648 <= out <= 2147483647 else 0

Example 2, traced

Input
x = -123

Output
-321

Why it works

The answer always holds the digits removed so far, in the order they were removed, and that order is the original number read backward. The loop ends when no digit is left, so the answer is then the full reverse. Zeros at the front vanish by themselves: for 120 the answer goes 0, 2, 21. The sign and the range are dealt with once, at the end.

Time and space

Time O(log |x|), extra space O(1). The loop runs once per digit of x (not at all for 0), at most 10 times. Ten times larger means one more digit: that slow growth is what log means, so the time is O(log |x|), with |x| meaning x without its sign. Two numbers are stored: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Take the sign off before the loop. With a negative number left in, the loop never ends in JavaScript or in Python: -1 divided by 10 and rounded down is -1 again, so the number never reaches 0.
• Round the division down. With plain division, in JavaScript or Python, 123 becomes 12.3, then 1.23, and takes hundreds of rounds to reach 0. By then the answer has become infinity, so every input except 0 returns 0.
• Check the range. Without the check, 1,534,236,469 returns 9,646,324,351 instead of 0. In JavaScript, cutting the answer to 32 bits with | 0 is no substitute: it wraps 9,646,324,351 around to 1,056,389,759, which looks like a valid answer.

Pattern

Digit-by-digit arithmetic. Builds on Happy Number and Add Two Numbers.

Keep going