Interview Prep Warmup: Reverse Integer via LeetCode in PHP

This problem was originally solved on LeetCode.

Given a 32-bit signed integer, reverse digits of an integer.

Note:
Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

Example 4:

Input: x = 0
Output: 0

The Problem: LeetCode’s Reverse Integer

This is another good problem to get warmed up on.

The question is asking us if we can reverse an integer. That’s easy.

Can we do so while respecting the limits of our operating system?

Absolutely!

If you’re following along in PHP: it is possible and acceptable to cast the integer as a string and operate on it that way.

In fact: my originally accepted solution did exactly that.

I’ll leave it as an exercise for the reader to implement, but it was a fun solution to write.

A faster, and possibly more elegant, solution is to use simple math to get the job done.

Using math we are going to “pop” each least significant digit off of the number and “push” it back into our result.

Popping and Pushing the Least Significant Digit

How do you “pop” the least significant digit of an integer?

$pop = $x % 10;
$x = intval($x / 10);

The variable $pop now holds the least significant digit, and the number has been shifted to the right by one space.

In PHP you’ll need to manually cast the resulting $x variable back to an integer so that it rounds properly.

The float rounding functions in PHP do not round towards 0, which is the behavior we need.

If it’s not clear why: -2 is considered “smaller” than -1 for the purposes of the integer rounding functions.

Because of this: intval(-1.2) and round(-1.2) return -1 and -2 respectively.

Since I am shifting digits by taking the modulus of 10 I already have stored the “rounded” value and need it dropped rather than rounded.

Thus: round-towards-zero is our goal, and we manually cast to an integer using intval.

Notice: this explanation and step would be irrelevant in a type safe language like Java.

Now I push that digit onto my result.

$res = ($res * 10) + $pop;

This simple code shifts the current value to the left, and puts our popped digit back into the least significant place.

Since we are working backwards through the input number our result will be in reverse order.

Checking for Integer Overflows

Because we know we are working with a 32 bit signed integer: we need to verify that our result is within those bounds.

A 32-bit signed integer ranges from -(231) <= x <= (231) - 1 and an easy solution is just to check for this after we’ve computed the result.

Is there any way we can quit early if we know we’re going to overflow?

First: go back to the math.

The result will overflow when we push it back onto the stack if:

  • $res >= 231
  • $res < -231

Since we multiply by 10 on every step we can predict whether we will cross that boundary in the current step.

If we will cross it, or if we’ve already passed it, quit and return 0.

The basic logic is implemented here and in the solution posted below.

Try to understand why this works before you move on.

$max = intval( 2147483647 / 10 );
$min = intval( -2147483648 / 10 );
// Before we push $pop and multiply by 10, check to see if that would cause overflow.
// If so, quit while we're still ahead.
if ($res > $max || ($r == $max && $pop > 7)) { // The 7 comes from the LSD in 2147483647
    return 0; 
}
if ($res < $min || ($r == $min && $pop < -8)) { // The 8 comes from the LSD in -2147483648
    return 0; 
}
// Push $pop onto $res

My Solution to the Reverse Integer Problem

Here’s my solution. It’s written in PHP and runs in O(logn) time.

    function reverse($x) {
        $r = 0;
        
        $max = intval( 2147483647 / 10 );
        $min = intval( -2147483648 / 10 );
        
        while ($x != 0) {
            $pop = $x % 10;
            $x = intval($x / 10); 
            if ($r > $max || ($r == $max && $pop > 7)) {
                return 0; 
            }
            if ($r < $min || ($r == $min && $pop < -8)) { 
                return 0; 
            }
            $r = ($r*10) + $pop;
        }
        
        return $r;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *