Implement Atoi

Given a string s, the objective is to convert it into integer format without utilizing any built-in functions. Refer the below steps to know about atoi() function.

Cases for atoi() conversion:

1. Skip any leading whitespaces.
2. Check for a sign (‘+’ or ‘-‘), default to positive if no sign is present.
3. Read the integer by ignoring leading zeros until a non-digit character is encountered or end of the string is reached. If no digits are present, return 0.
4. If the integer is greater than 2³¹ – 1, then return 2³¹ – 1 and if the integer is smaller than -2³¹, then return -2³¹.

Examples:

Input: s = "-123"
Output: -123
Explanation: It is possible to convert -123 into an integer so we returned in the form of an integer

Input: s = "  -"
Output: 0
Explanation: No digits are present, therefore the returned answer is 0.

Input: s = " 1231231231311133"
Output: 2147483647
Explanation: The converted number will be greater than 231 – 1, therefore print 231 – 1 = 2147483647.

Input: s = "-999999999999"
Output: -2147483648
Explanation: The converted number is smaller than -231, therefore print -231 = -2147483648.

Input: s = "  -0012gfg4"
Output: -12
Explanation: Nothing is read after -12 as a non-digit character ‘g’ was encountered.

Constraints:
1 ≤ |s| ≤ 15

Approach 01:

#include <climits> // For INT_MAX and INT_MIN
#include <cstring> // For strlen

class Solution {
public:
    int myAtoi(char* s) {
        // Step 1: Skip leading spaces
        while (*s == ' ')
            ++s;

        // Step 2: Determine the sign
        bool isNegative = false;
        if (*s == '-') {
            isNegative = true;
            ++s;
        } else if (*s == '+') {
            ++s;
        }

        // Step 3: Convert the string to an integer
        long long result = 0; // Use long long to handle overflow

        while (*s >= '0' && *s <= '9') {
            result = result * 10 + (*s - '0');
            
            // Step 4: Check for overflow conditions
            if (result > INT_MAX) {
                return isNegative ? INT_MIN : INT_MAX;
            }

            ++s;
        }

        // Step 5: Apply the sign
        if (isNegative) {
            result = -result;
        }

        return static_cast<int>(result);
    }
};

class Solution:
    def myAtoi(self, string):
        # Remove leading and trailing spaces
        trimmedString = string.strip()
        isNegative = False
        result = 0

        # Check for negative sign
        if trimmedString[0] == '-':
            isNegative = True
            trimmedString = trimmedString[1:]

        # Convert the string to an integer
        for char in trimmedString:
            if(char > '9' or char < '0'):
                break
            result = result * 10 + int(char)
            # Check for overflow conditions
            if result > (2**31 - 1):
                if not isNegative:
                    return 2**31 - 1
            if (isNegative and (result > (2**31))):
                return -2**31

        if isNegative:
            return -result
        return result

Time Complexity

• Skipping Leading Spaces:

  The function iterates through the leading spaces in the input string, taking \( O(L) \), where \( L \) is the length of the string in the worst case.

• Processing Numeric Characters:

  The loop iterates through the numeric characters in the string, converting them into an integer. This also takes \( O(L) \) in the worst case since the loop stops as soon as non-numeric characters are encountered.

• Overall Time Complexity:

  The overall time complexity is \( O(L) \), where \( L \) is the length of the input string, as the operations are performed sequentially.

Space Complexity

• Input String:

  The function processes the input string in-place without creating any additional copies, so no extra space is used.

• Variables:

  A constant amount of extra space is used for variables like result, isNegative, and the pointer s.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \), as the function uses only a constant amount of extra space.