Solving the 'String to Integer (atoi)' on LeetCode with C++

Problem

https://leetcode.com/problems/string-to-integer-atoi/

Answer

#include <string>
#include <climits>

class Solution {
public:
    int myAtoi(string s) {
        int i = 0, sign = 1, result = 0;

        // Skip whitespaces
        while (i < s.size() && s[i] == ' ') {
            i++;
        }

        // Check the sign
        if (i < s.size() && (s[i] == '-' || s[i] == '+')) {
            sign = (s[i++] == '-') ? -1 : 1;
        }

        // Read in the digits and check for overflow/underflow condition
        while (i < s.size() && isdigit(s[i])) {
            if (result > INT_MAX / 10 || (result == INT_MAX / 10 && s[i] - '0' > INT_MAX % 10)) {
                return (sign == 1) ? INT_MAX : INT_MIN;
            }
            result = result * 10 + (s[i++] - '0');
        }

        return result * sign;
    }
};

Let's analyze the solution to the problem.

Assume the input is " -45string".

1.Read in and ignore any leading whitespace.

We need to convert " -45string" to "-45string", resulting in "-45string".

2.Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.

We need to check whether a sign is positive or negative.
The '-' sign is temporarily stored and the input becomes "45string".

Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.

We check each character in order, until a non-digit character is encountered.

The input becomes "45".

Finally, we convert the string to an integer and add the sign (positive or negative).

The final output is -45.

Additionally, we must ensure that the integer does not exceed the limits of INT_MAX and INT_MIN.

If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.

To adhere to the above constraints, we add conditions to the code.

Let's break down the code.

#include <string>
#include <climits>

class Solution {
public:
    int myAtoi(string s) {
        int i = 0, sign = 1, result = 0;

        // Skip whitespaces
        while (i < s.size() && s[i] == ' ') {
            i++;
        }

        // Check the sign
        if (i < s.size() && (s[i] == '-' || s[i] == '+')) {
            sign = (s[i++] == '-') ? -1 : 1;
        }

        // Read in the digits and check for overflow/underflow condition
        while (i < s.size() && isdigit(s[i])) {
            if (result > INT_MAX / 10 || (result == INT_MAX / 10 && s[i] - '0' > INT_MAX % 10)) {
                return (sign == 1) ? INT_MAX : INT_MIN;
            }
            result = result * 10 + (s[i++] - '0');
        }

        return result * sign;
    }
};

        while (i < s.size() && s[i] == ' ') {
            i++;
        }

Only the space character ' ' is considered a whitespace character.

We skip white spaces using s[i] == ' ' because the above constrain.

        if (i < s.size() && (s[i] == '-' || s[i] == '+')) {
            sign = (s[i++] == '-') ? -1 : 1;
        }

Here, the sign is stored as 1 or -1 and then multiplied by the result. This way, the sign is reflected in the result.

        while (i < s.size() && isdigit(s[i])) {
            if (result > INT_MAX / 10 || (result == INT_MAX / 10 && s[i] - '0' > INT_MAX % 10)) {
                return (sign == 1) ? INT_MAX : INT_MIN;
            }
            result = result * 10 + (s[i++] - '0');
        }

The while loop condition checks if i is less than s.size() and if s[i] is a digit.

If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.

We need to return INT_MAX or INT_MIN if result exceeds these limits.

The condition result > INT_MAX / 10 will return INT_MAX or INT_MIN if the result is greater than INT_MAX / 10. This is due to the multiplication of result and 10 in the last line of the condition.

The second condition result == INT_MAX / 10 && s[i] - '0' > INT_MAX % 10 will return INT_MAX or INT_MIN if the result equals INT_MAX / 10 and s[i] is greater than INT_MAX % 10. This is because result * 10 is increased by s[i++] - '0'.

Let's simplify the explanation:

The condition result == INT_MAX / 10 && s[i] - '0' > INT_MAX % 10 is checking if the current number (result) is about to exceed the maximum limit for an integer (INT_MAX).

INT_MAX is the maximum value an integer can hold, which is 2147483647.

The condition result == INT_MAX / 10 is checking if result is equal to the largest possible integer divided by 10, which is 214748364.

The condition s[i] - '0' > INT_MAX % 10 is checking if the current digit of the string (where '0' is subtracted to convert from ASCII to numeric value) is greater than the remainder of INT_MAX divided by 10, which is 7.

If result equals 214748364 (INT_MAX / 10) and the next digit is greater than 7, adding that digit to result would cause it to exceed the maximum value for an integer.

For example, if result is 214748364 and the next digit is 8:

Multiplying result by 10 gives 2147483640.

Adding 8 (the next digit) gives 2147483648.

2147483648 is greater than INT_MAX (2147483647), so it would exceed the limit.

`result == INT_MAX / 10 && s[i] - '0' > INT_MAX % 10`

result == INT_MAX / 10 
result == INT_MAX(2147483647) / 10 
result == 214748364

s[i] - '0' > INT_MAX % 10` 
s[i] - '0' > INT_MAX(2147483647) % 10 
s[i] - '0' > 7

The result will exceed INT_MAX if `result` equals INT_MAX / 10 (214748364) and `s[i] - '0'` is greater than 7.

For instance:
result = 214748364
s[i] = '8'

result * 10 + s[i++] - '0'
2147483640 + 8 
2147483648

The result 2147483648 exceeds INT_MAX.