Hello, Welcome to my Day 8 of #30Days of Problem Solving and finding solutions to Leetcode's Data Structures and Algorithm questions. Here, I choose a question daily and try to solve it, and finally pen down my process of flow in solving the question.

I hope you find it helpful. Today I will be solving Leetcode's question 7 -Reverse A String

Problem Statement

• 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<sup>31</sup>, 2<sup>31</sup> - 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
  

  Thought Process/ Intuition

My first thoughts on how to solve this problem would be to convert the integer to a string, reverse the string, and convert it back to an integer. However, this solution would not work in the case of an overflow, as the resulting integer may exceed the 32-bit integer range.

To solve this problem while avoiding the overflow issue, I would need to reverse the integer using only mathematical operations without converting it to a string. One approach would be to repeatedly extract the last digit of the input integer using modulo division, then add each extracted digit to the reversed integer after shifting the digits one place to the left using multiplication by 10. I would also need to check for overflow after each addition to ensure that the resulting integer remains within the 32-bit integer range.

The Approach

The approach I would use to solve this problem is to repeatedly extract the last digit of the input integer using modulo division, then add each extracted digit to the reversed integer after shifting the digits one place to the left using multiplication by 10. To handle negative input integers, I would first check if the input integer is negative and set a flag accordingly, then convert the input integer to its absolute value for the rest of the operations.

After reversing the integer, I would check if the resulting integer is within the 32-bit integer range. To do this, I would compare the reversed integer to the upper and lower limits of the 32-bit integer range. If the reversed integer is outside this range, I would return 0 as required by the problem statement. If the reversed integer is within the range, I would return it.

Overall, this approach avoids using string operations to reverse the integer and ensures that the resulting integer is within the 32-bit integer range, meeting the requirements of the problem statement.

There are two solutions to this problem. The first solutin offers the mathematical solution whereas the secode one explores the string operation

Solution 1

class Solution:
    def reverse(self, x: int) -> int:
        rev_number = 0                            
        is_negative = x < 0                    
        x = abs(x)
        while x > 0:
          remainder = x % 10
          rev_number = rev_number * 10 + remainder
          x //= 10
        if is_negative:
            rev_number = -rev_number
        if rev_number < -2**31 or rev_number > 2**31 - 1:
            return 0
        return rev_number

The Solution class is just a container for the reverse() method, which takes an integer x as input and returns an integer as output.

We use the same implementation as before, where we extract digits from x using the modulo operator % and add them to the result after multiplying by 10 and adding the digit. We check if the input integer is negative, and if so, we convert it to a positive number using the abs() function. We update x by dividing it by 10 using integer division //.

After the loop, we check if the input integer was originally negative and adjust the result accordingly. Finally, we check if the result is within the signed 32-bit integer range and return 0 if it is not.

Note that we don't need to use the self parameter in this implementation, as we are not using any class-level attributes or methods. However, we keep it here to match the given method signature.

Solution 2

class Solution:
    def reverse(self, x: int) -> int:
        #convert the interger to as tring and check if its negative
        is_negative = False 
        if x < 0:
            is_negative = True 
            x *= -1
        str_x = str(x)
        # reversethe string
        reversed_str = str_x[::-1]

        #convert the reversed string back to an interger
        reversed_int = int(reversed_str)
        #if the original interger was negative, make the reversed interger negative
        if is_negative:
            reversed_int *= -1
        #check if the reversed interger is within the 32-bit integer range
        if reversed_int < -2**31 or reversed_int > 2**31 - 1:
            return 0

        return reversed_int

The code takes an integer input and converts it into a string, reverses the string, and converts it back to an integer. If the original integer was negative, the final integer is also negative. The code checks if the final integer is within the 32-bit integer range and returns 0 if it's not. Otherwise, it returns the reversed integer.

Complexity Of the 2 solutions

The time complexity of the mathematical operation approach is O(log(x)), where x is the input integer. This is because we need to extract each digit from the input integer, and the number of digits in the input integer is proportional to its logarithm. The space complexity of this approach is O(1), as we are only using a constant amount of additional space to store the reversed integer and some variables.

On the other hand, the time complexity of the approach that uses string operations is O(n), where n is the length of the input integer when converted to a string. This is because we need to reverse the string, which requires iterating over each character of the string. The space complexity of this approach is also O(n), as we need to create a new string to store the reversed integer.

In terms of efficiency, the mathematical operation approach is generally faster, especially for large input integers, since it requires fewer operations and less memory. However, the string operation approach may be simpler to understand and implement.

Conclusion

In conclusion, both solutions aim to reverse the digits of an input integer, but they take different approaches to achieve the same result.

The first solution uses mathematical operations to reverse the integer digit by digit, while the second solution converts the integer to a string, reverses the string, and converts it back to an integer.

Both solutions have a time complexity of O(log n), where n is the magnitude of the input integer. However, the first solution has a space complexity of O(1) since it only uses a constant amount of memory, while the second solution has a space complexity of O(log n) due to the string conversion.

The second solution is more readable and easier to understand, but it may be less efficient for very large input integers. The first solution is more efficient but may be harder to understand for someone who is not familiar with the math involved.