004.md

7. Reverse Integer

Difficulty: 🟡 Medium

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Examples:

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

Constraints:

• -2^31 <= x <= 2^31 - 1

Solutions

O(n) solution

Python3

class Solution:
    def reverse(self, x: int) -> int:
        number, reversed_number = abs(x), 0
        while number:
            reversed_number = reversed_number*10 + number%10
            number //= 10

        reversed_number *= -1 if x < 0 else 1

        if -2**31 <= reversed_number <= 2**31-1:
            return reversed_number
        return 0

The given solution solves the problem by using a while loop to reverse the digits of the input number x. It checks if the reversed number falls within the valid range and returns the reversed number if it does, or returns 0 otherwise.

The algorithm follows these steps:

1. Define variables number and reversed_number initialized to the absolute value of x and 0, respectively.
2. Enter a while loop that continues as long as number is non-zero.
3. Inside the while loop, calculate the next digit of the reversed number by using the expression reversed_number = reversed_number * 10 + number % 10, where number % 10 gives the last digit of number and reversed_number * 10 shifts the existing digits to the left.
4. Divide number by 10 using the floor division operator number //= 10 to remove the last digit.
5. Repeat steps 3-4 until number becomes zero.
6. Multiply the reversed_number by -1 if x is negative, otherwise multiply it by 1 to preserve the sign.
7. Check if the reversed_number falls within the range [-2^31, 2^31 - 1]. If it does, return the reversed_number; otherwise, return 0.

Complexity Analysis

The time complexity of the algorithm is O(D), where D is the number of digits in the input number x. This is because the algorithm iterates through each digit of x in the while loop, performing constant-time operations.

The space complexity of the algorithm is O(1) because it uses a constant amount of additional space to store the number and reversed_number variables.

Summary

The given solution reverses the digits of a signed 32-bit integer x and returns the reversed number. The algorithm uses a while loop to iterate through each digit of x, calculates the reversed number, and checks if it falls within the valid range. The algorithm has a time complexity of O(D) and a space complexity of O(1), where D is the number of digits in x.

User suggested solutions in other languages

TypeScript

function reverse(x: number): number {
  const isNegative = x < 0;

  let num = Math.abs(x);
  let reversedNumber = 0;

  while (num > 0) {
    let lastDigit = num % 10;
    reversedNumber = reversedNumber * 10 + lastDigit;
    num = Math.floor(num / 10);
  }

  const result = isNegative ? -reversedNumber : reversedNumber;

  if (result > 2 ** 31 - 1 || result < -(2 ** 31)) return 0;

  return result;
}

Php

class Solution {

    /**
     * @param Integer $x
     * @return Integer
     */
    function reverse(int $x) {
        $number = abs($x);
        $reversedNumber = 0;
        
        while ($number > 0) {
            $reversedNumber = $reversedNumber * 10 + $number % 10;
            $number = (int)($number / 10);
        }
        
        $reversedNumber *= ($x < 0) ? -1 : 1;
        
        if (-pow(2, 31) <= $reversedNumber && $reversedNumber <= pow(2, 31) - 1) {
            return $reversedNumber;
        }
        
        return 0;
     
    }
}

NB: If you want to get community points please suggest solutions in other languages as merge requests.