LeetCode 8: String to Integer (atoi)

Python

We use lstrip() to get rid of spaces from the beginning. In Python, the int does not overflow or underflow. So, if num is too big or too small, we just cap the magnitude at the 32-bit positive’s max ( $2^{31}-1$ ) or negative’s max ( $2^{31}$ ).

Time: $\mathcal{O}(n)$ , space: $\mathcal{O}(n)$ . Without lstrip, space would have been $\mathcal{O}(1)$ .

class Solution:
    def myAtoi(self, s: str) -> int:
        s = s.lstrip()
        if not s:
            return 0
        
        sign = -1 if s[0] == "-" else 1
        begin = 1 if s[0] in "+-" else 0
        num = 0
        max_mag = pow(2, 31)
        for i in range(begin, len(s)):
            c = s[i]
            if not c.isdigit():
                break
            if num == 0 and c == "0":
                continue

            num = 10*num + int(c)
            if num > max_mag-1 and sign == 1:
                num = max_mag-1
                break
                
            if num > max_mag and sign == -1:
                num = max_mag
                break

        return sign * num

C++

We want to detect overflow or underflow before it happens. So, we would imagine what would happen to num if we did (num = 10 * num + digit) without actually doing it.

Since in each iteration we multiply num by 10, if $\texttt{num} > \frac{2^{31}}{10}$ , then no more digits can be included. If $\texttt{num} = \frac{2^{31}}{10}$ , depending on the current digit’s value, we might still be able to include the current digit.

Note, $2^{31} \equiv \left( 2^{10} \right)^3 \cdot 2 \equiv 4^3 \cdot 2 \equiv 8 \ (\texttt{mod } 10)$ .

So, the last digit of $2^{31}$ is $8$ and the last digit of $2^{31} - 1$ is $7$ . When $\texttt{num} = \frac{2^{31}}{10}$ , if the sign is positive, we need the current digit to be $\le 7$ for it to be included. On the other hand, if the sign is negative, we need the current digit to be $\le 8$ .

Time: $\mathcal{O}(n)$ , space: $\mathcal{O}(1)$ .

class Solution {
public:
    int myAtoi(string s) {
        auto n = s.size();
        auto begin = 0;
        while (begin < n and s[begin] == ' ') {
            ++begin;
        }

        if (begin == n) {
            return 0;
        }

        auto sign = (s[begin] == '-') ? -1 : 1;
        begin = (s[begin] == '+' or s[begin] == '-') ? begin + 1 : begin;
        int32_t num = 0;
        uint32_t max = (1U << 31) - 1;
        uint32_t min = -(1U << 31);
        uint32_t max_mag_tenth = (1U << 31) / 10;
        for (auto i = begin; i < n; ++i) {
            auto c = s[i];
            if (not isdigit(c)) {
                break;
            }
            if (num == 0 and c == '0') {
                continue;
            }
            if (num > max_mag_tenth) {
                return (sign == 1) ? max : min;
            }
            
            auto digit = c - '0';
            if (num == max_mag_tenth) {
                if (sign == 1 and digit >= 7) {
                    return max;
                }
                if (sign == -1 and digit >= 8) {
                    return min;
                }
            }
            num = 10 * num + digit;
        }

        return sign * num;
    }
};

Above, we use uint32_t only to be able to find the max or min values. We could hard code these extremes and thus get away with just int32_t.

class Solution {
public:
    int myAtoi(string s) {
        auto n = s.size();
        auto begin = 0;
        while (begin < n and s[begin] == ' ') {
            ++begin;
        }

        if (begin == n) {
            return 0;
        }

        auto sign = (s[begin] == '-') ? -1 : 1;
        begin = (s[begin] == '+' or s[begin] == '-') ? begin + 1 : begin;
        int32_t num = 0;
        int32_t max = 2'147'483'647;
        int32_t min = -2'147'483'648;
        int32_t max_mag_tenth = 2'147'483'64;
        for (auto i = begin; i < n; ++i) {
            auto c = s[i];
            if (not isdigit(c)) {
                break;
            }
            if (num == 0 and c == '0') {
                continue;
            }
            if (num > max_mag_tenth) {
                return (sign == 1) ? max : min;
            }
            
            auto digit = c - '0';
            if (num == max_mag_tenth) {
                if (sign == 1 and digit >= 7) {
                    return max;
                }
                if (sign == -1 and digit >= 8) {
                    return min;
                }
            }
            num = 10 * num + digit;
        }

        return sign * num;
    }
};

Or, we can make num of type uint64_t and check if the number is too big or too small without worrying about overflow or underflow.

class Solution {
public:
    int myAtoi(string s) {
        auto n = s.size();
        auto begin = 0;
        while (begin < n and s[begin] == ' ') {
            ++begin;
        }

        if (begin == n) {
            return 0;
        }

        auto sign = (s[begin] == '-') ? -1 : 1;
        begin = (s[begin] == '+' or s[begin] == '-') ? begin + 1 : begin;
        uint64_t num = 0;
        uint32_t max_mag = 1U << 31;
        for (auto i = begin; i < n; ++i) {
            auto c = s[i];
            if (not isdigit(c)) {
                break;
            }
            if (num == 0 and c == '0') {
                continue;
            }
            
            num = 10 * num + (c-'0');
            if (sign == 1 and num > max_mag-1) {
                return max_mag-1;
            }
            if (sign == -1 and num > max_mag) {
                return -max_mag;
            }
        }

        return sign * num;
    }
};

unreasonably effective