2 min to read
Reverse Integer Algorithm in C++, Java, and Python - LeetCode Problem
Reverse Integer is the medium-level problem of LeetCode. In this post, we will see the solution to 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 //= 10operation takes constant time. - The if statement takes constant time.
- The
rev = rev * 10 + popoperation 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).
