String to Integer Conversion

The main challenge in string-to-integer conversion lies in overflow detection.

Here’s the approach: Take the extreme values and remove their last digit (divide by 10). If your current number is already larger than this truncated value, adding the final digit will cause overflow. If they’re equal, compare the last digits - if the incoming digit is larger, it will overflow.

Time complexity: O(n) Space complexity: O(1)

int myAtoi(string str) {
    if (str.empty()) return 0;

    bool isMinus=false;
    int pos=0;
    // Skip spaces
    while(str[pos] == ' ') ++pos;
    // Check and skip sign
    if (str[pos] == '-' || str[pos] == '+')
        if (str[pos++] == '-') isMinus = true;

    int number=0;
    static int ma = INT_MAX/10;
    static int ma_l = INT_MAX%10;
    static int mi = (unsigned)INT_MIN/10;
    static int mi_l = (unsigned)INT_MIN%10;

    // Start conversion
    while(str[pos] >= '0' && str[pos]<='9') {
        int c = str[pos++]-'0';
        // Check upper and lower overflow
        if (!isMinus && (number > ma || (number == ma && c>ma_l))) {
            return INT_MAX;
        }
        else if
        (isMinus && (number > mi || (number == mi && c > mi_l)))
        {
            return INT_MIN;
        }
        number = 10*number + c;
    }

    return isMinus ? -number : number;
}

If you don’t want to handle overflow checks manually, you can use a long type for the number variable and directly compare it with INT_MAX and INT_MIN.

Key takeaways

INT_MIN and INT_MAX macros are available in #include<bits/stdc++.h>
Overflow detection techniques

#overflow

String Rotation and Reversal Techniques Sudoku Solver