[LeetCode] 7. Reverse Integer

Problem

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).

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

Solution

Algorithm

Complexity Analysis

• Time Complexity

x(n)의 자리 수와 동일한 반복횟수로 while반복문(4)이 실행되므로 x(n)의 자리수를 구하면 된다. x(n)의 자리수는 x(n)에 log를 취하고 1을 더해주면 된다. 따라서 모든 경우에 O(logn + 1)의 시간 복잡도를 가진다. (소수점 버림)

• Space Complexity

x의 크기에 따라 감소하거나 증가되어 할당받는 공간 없이 일정한 공간을 할당받으므로 모든 경우에 O(1)의 공간 복잡도를 가진다.