LESSON 563 OF 639 · MATH

Reverse Integer in Scala

Practice O(log |x|)

You get a whole number x that fits in 32 bits. Return x with its digits in reverse order.

A minus sign stays in front. Zeros that end up at the start of the result are dropped.

32-bit integers go from -2,147,483,648 to 2,147,483,647. If the reversed number is outside that range, return 0.

Solve it without a 64-bit integer type.

Example 1:

Input: x = 5600
Output: 65
Explanation: Reversed, the digits read 0065.
The two zeros in front are dropped.

Example 2:

Input: x = -2408
Output: -8042
Explanation: The digits 2408 reversed are 8042.
The minus sign stays.

Example 3:

Input: x = 1000000009
Output: 0
Explanation: Reversed, it would be 9,000,000,001.
That is more than 2,147,483,647, so the answer is 0.

Constraints:

x is from -2,147,483,648 to 2,147,483,647.
In powers of two, that is -2³¹ to 2³¹ − 1.

Note:

Your solution should run in O(log |x|) time and use O(1) extra space.

Take the digits from the right, one at a time. The remainder of a division by 10 is the last digit. Dividing by 10 drops it. Each digit goes at the end of the result: result * 10 + digit.

Check before you add each digit. If result is already above 214,748,364, ten times it is too big. If it equals 214,748,364, the digit can be at most 7. Negative numbers work the same way, with -214,748,364 and -8.

Each digit takes one step, and x has about log₁₀|x| digits, at most 10: O(log |x|) time.
Only a few numbers are kept, so the extra space is O(1).

STEP 1 OF 9

Guided

Ctrl + Enter to check