Reverse Integer Algorithm in C++, Java, and Python - LeetCode Problem

Reverse Integer is medium level problem of LeetCode. In this post, we will see the solution of this problem in C++, Java, and Python.

Problem Statement and Explanation

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.

Example 1:

input: 134
output: 431

Example 2:

input: -312
output: -213

Reverse Integer Python Solution in Python

Reverse Integer Java Solution in Java

Reverse Integer C++ Solution in C++

Explanation of Solution

• The while loop iterates until the number x is 0.
• In each iteration, the function pops the last digit off the number x and stores it in the variable pop.
• The number x is then divided by 10.
• The function checks if the reversed number rev is greater than INT_MAX or less than INT_MIN. If it is, the function returns 0.
• The reversed number rev is then multiplied by 10 and the last digit pop is added back.
• The function returns the reversed number rev.

Time Complexity of the Solution

The time complexity of the solution is O(n), where n is the number of digits in the original number. This is because the while loop iterates n times.

Here is a breakdown of the time complexity of each step in the function:

• The while loop iterates n times.
• The pop operation takes constant time.
• The x //= 10 operation takes constant time.
• The if statement takes constant time.
• The rev = rev * 10 + pop operation takes constant time.
• Therefore, the total time complexity of the function is O(n).

Space Complexity of the Solution

The space complexity of the solution is O(1), since the function only uses a constant number of variables. Here is a breakdown of the space complexity of each step in the function:

• The rev variable is a local variable and only needs to be stored on the stack.
• The pop variable is a local variable and only needs to be stored on the stack.
• The if statement does not introduce any new variables.
• Therefore, the total space complexity of the function is O(1).

Problem statement is taken from Leet Code, and the solutions are implemented by CodePerfectPlus team.