Problem Statement
Given an integer, reverse its digits and return the reversed integer.
Example
-
Input: reverse(123)
Output: 321
-
Input: reverse(-456)
Output: -654
-
Input: reverse(100)
Output: 1
Brute Force Approach
Approach
Idea: Convert the number to a string, reverse the string, and convert it back to an integer. Handle negative numbers by reversing the digits and restoring the negative sign.
Steps
- Convert the integer to a string.
- Reverse the string using JavaScript's array operations.
- Convert the reversed string back to an integer.
- If the original number was negative, reapply the negative sign to the result.
- Return the reversed integer.
Time & Space Complexity
- Time Complexity: O(d), where
d is the number of digits in the number.
- String and array operations are linear in the number of digits.
- Space Complexity: O(d)
- Temporary storage for the string and reversed digits.
Code Snippet
Dry Run
Input: num = -456
- Identify that
num is negative.
- Convert
456 to string "456".
- Reverse the string to get
"654".
- Convert back to integer
654 and reapply the negative sign.
- Return
-654.
Efficient Approach Without Using String Conversion
Approach
Idea: Use arithmetic operations to extract digits from the number, construct the reversed number, and handle negatives.
Steps
- Initialize
reversedNum = 0.
- While the number is not
0, repeatedly:
- Extract the last digit using
num % 10.
- Append it to
reversedNum by multiplying reversedNum by 10 and adding the extracted digit.
- Remove the last digit from
num by performing integer division (Math.floor(num / 10)).
- Return
reversedNum.
Time & Space Complexity
- Time Complexity: O(d), where
d is the number of digits in the number.
- Each digit is processed once.
- Space Complexity: O(1)
- Only a few variables are used.
Code Snippet
Dry Run
Input: num = 123
- Initialize
reversedNum = 0.
- Loop through digits:
- Extract
3 (123 % 10), update reversedNum = 0 * 10 + 3 = 3, reduce num = 12.
- Extract
2 (12 % 10), update reversedNum = 3 * 10 + 2 = 32, reduce num = 1.
- Extract
1 (1 % 10), update reversedNum = 32 * 10 + 1 = 321, reduce num = 0.
- Return
321.
Complexity Analysis
| Operation | Brute Force | Efficient Approach |
|---|
| Time Complexity | O(d) | O(d) |
| Space Complexity | O(d) | O(1) |
Conclusion
- The brute force approach uses string manipulation, which is simple to implement but requires additional space for strings.
- The efficient approach avoids string conversion and uses arithmetic operations to achieve O(1) space complexity.
- This problem highlights the trade-off between simplicity and optimization when working with numeric data.