Problem Statement: String to Integer (atoi)

Implement the function atoi which converts a string to an integer. The function should follow these rules:

1. Ignore leading whitespace.
2. Optional sign: The string may start with an optional ‘+’ or ‘-‘ sign.
3. Valid numeric characters: The string may contain digits, and the function should convert the numeric characters to an integer. Once a non-digit character is encountered, the conversion should stop.
4. Overflow and Underflow: If the result overflows or underflows a 32-bit signed integer, return the respective boundary values:
   • Integer overflow: 2147483647
   • Integer underflow: -2147483648
5. Return 0 for invalid input: If no valid conversion could be made, return 0.

Example:

Example 1:

• Input: "42"
• Output: 42

Example 2:

• Input: " -42"
• Output: -42

Example 3:

• Input: "4193 with words"
• Output: 4193

Example 4:

• Input: "words and 987"
• Output: 0

Example 5:

• Input: "-91283472332"
• Output: -2147483648 (since it overflows the 32-bit signed integer)

Approach:

1. Whitespace Handling: Start by skipping any leading whitespace characters.
2. Optional Sign: Check if the string starts with a ‘+’ or ‘-‘ sign. If there’s a sign, we need to remember it.
3. Conversion of Digits: Iterate through the characters, convert them to integers and build the result by multiplying the current number by 10 and adding the current digit.
4. Overflow/Underflow Handling: As you build the integer, check if the result exceeds the 32-bit integer range, and return the appropriate boundary values.
5. Edge Case: If no digits are encountered, return 0.

Algorithm:

1. Ignore leading whitespaces.
2. Check for an optional sign (‘+’ or ‘-‘).
3. Convert the digits one by one, updating the result.
4. Handle overflow and underflow at each step.
5. Return the result.

Time Complexity:

• Time complexity: O(n), where n is the length of the string. We iterate over the string once.
• Space complexity: O(1), since we use only a few variables to store the result.

---

Code Implementation:

C:

#include <stdio.h>
#include <limits.h>
#include <ctype.h>

int myAtoi(char* str) {
    long result = 0;
    int i = 0, sign = 1;

    // Skip leading whitespaces
    while (str[i] == ' ') i++;

    // Check for optional sign
    if (str[i] == '+' || str[i] == '-') {
        sign = (str[i] == '-') ? -1 : 1;
        i++;
    }

    // Convert digits to integer
    while (isdigit(str[i])) {
        result = result * 10 + (str[i] - '0');
        i++;

        // Check for overflow/underflow
        if (result * sign > INT_MAX) return INT_MAX;
        if (result * sign < INT_MIN) return INT_MIN;
    }

    return (int)(result * sign);
}

int main() {
    char str[] = "  -42";
    printf("%d\n", myAtoi(str));
    return 0;
}

C++:

#include <iostream>
#include <climits>
#include <cctype>

using namespace std;

int myAtoi(string str) {
    long result = 0;
    int i = 0, sign = 1;

    // Skip leading whitespaces
    while (i < str.size() && str[i] == ' ') i++;

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

    // Convert digits to integer
    while (i < str.size() && isdigit(str[i])) {
        result = result * 10 + (str[i] - '0');
        i++;

        // Check for overflow/underflow
        if (result * sign > INT_MAX) return INT_MAX;
        if (result * sign < INT_MIN) return INT_MIN;
    }

    return (int)(result * sign);
}

int main() {
    string str = "  -42";
    cout << myAtoi(str) << endl;
    return 0;
}

Java:

public class Solution {
    public int myAtoi(String str) {
        long result = 0;
        int i = 0, sign = 1;

        // Skip leading whitespaces
        while (i < str.length() && str.charAt(i) == ' ') i++;

        // Handle optional sign
        if (i < str.length() && (str.charAt(i) == '+' || str.charAt(i) == '-')) {
            sign = (str.charAt(i) == '-') ? -1 : 1;
            i++;
        }

        // Convert digits to integer
        while (i < str.length() && Character.isDigit(str.charAt(i))) {
            result = result * 10 + (str.charAt(i) - '0');
            i++;

            // Check for overflow/underflow
            if (result * sign > Integer.MAX_VALUE) return Integer.MAX_VALUE;
            if (result * sign < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        }

        return (int)(result * sign);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String str = "  -42";
        System.out.println(sol.myAtoi(str));
    }
}

Python:

def myAtoi(s: str) -> int:
    result = 0
    sign = 1
    i = 0

    # Skip leading whitespaces
    while i < len(s) and s[i] == ' ':
        i += 1

    # Handle optional sign
    if i < len(s) and (s[i] == '+' or s[i] == '-'):
        sign = -1 if s[i] == '-' else 1
        i += 1

    # Convert digits to integer
    while i < len(s) and s[i].isdigit():
        result = result * 10 + int(s[i])
        i += 1

        # Check for overflow/underflow
        if result * sign > 2**31 - 1:
            return 2**31 - 1
        if result * sign < -2**31:
            return -2**31

    return result * sign

# Example usage
s = "  -42"
print(myAtoi(s))

C#:

using System;

public class Solution {
    public int MyAtoi(string str) {
        long result = 0;
        int i = 0, sign = 1;

        // Skip leading whitespaces
        while (i < str.Length && str[i] == ' ') i++;

        // Handle optional sign
        if (i < str.Length && (str[i] == '+' || str[i] == '-')) {
            sign = (str[i] == '-') ? -1 : 1;
            i++;
        }

        // Convert digits to integer
        while (i < str.Length && Char.IsDigit(str[i])) {
            result = result * 10 + (str[i] - '0');
            i++;

            // Check for overflow/underflow
            if (result * sign > Int32.MaxValue) return Int32.MaxValue;
            if (result * sign < Int32.MinValue) return Int32.MinValue;
        }

        return (int)(result * sign);
    }

    public static void Main() {
        Solution sol = new Solution();
        string str = "  -42";
        Console.WriteLine(sol.MyAtoi(str));
    }
}

JavaScript:

var myAtoi = function(s) {
    let result = 0;
    let sign = 1;
    let i = 0;

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

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

    // Convert digits to integer
    while (i < s.length && /\d/.test(s[i])) {
        result = result * 10 + (s[i] - '0');
        i++;

        // Check for overflow/underflow
        if (result * sign > 2**31 - 1) return 2**31 - 1;
        if (result * sign < -(2**31)) return -(2**31);
    }

    return result * sign;
};

// Example usage
let s = "  -42";
console.log(myAtoi(s));