algoadvance

Leetcode 7. Reverse Integer

Problem Statement

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Clarifying Questions

  1. Q: How should the function behave when encountering a value outside the 32-bit integer range after reversing? A: The function should return 0 if the reversed integer overflows outside of the 32-bit signed integer range [−2^31, 2^31 − 1].

  2. Q: Are there any special characters or spaces in the input? A: No, the input would be a standard 32-bit signed integer.

  3. Q: Should we consider leading zeros in the input? A: No, leading zeros should be stripped in the output.

Strategy

  1. We will initialize a variable (reversed) to store the reversed number.
  2. We will process the given integer digit by digit using modulo and division operations.
  3. Before adding each digit to reversed, we will check if reversed might overflow when updated. This requires checking against INT_MAX / 10 and INT_MIN / 10.
  4. If it is safe to add the digit, we proceed. Otherwise, we should return 0 to indicate an overflow.

Code

#include <iostream>
#include <limits.h>

class Solution {
public:
    int reverse(int x) {
        int reversed = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            // Check for overflow before actually performing the multiplication and addition
            if (reversed > INT_MAX/10 || (reversed == INT_MAX / 10 && pop > 7)) return 0;
            if (reversed < INT_MIN/10 || (reversed == INT_MIN / 10 && pop < -8)) return 0;
            reversed = reversed * 10 + pop;
        }
        return reversed;
    }
};

int main() {
    Solution solution;
    std::cout << solution.reverse(123) << std::endl;  // Output: 321
    std::cout << solution.reverse(-123) << std::endl; // Output: -321
    std::cout << solution.reverse(120) << std::endl;  // Output: 21
    std::cout << solution.reverse(0) << std::endl;    // Output: 0
    // Overflow cases
    std::cout << solution.reverse(1534236469) << std::endl; // Output: 0
    return 0;
}

Time Complexity

The time complexity of this solution is O(log10(n)), where n is the input number. This is because we are processing each digit of the number once.

The space complexity is O(1), as we are using a constant amount of additional space regardless of the size of n.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI