Problem Statement
Implement myAtoi(s) to convert a string into a 32-bit signed integer.
Follow these rules:
Skip all leading spaces (
' ').Read one optional sign (
'-'or'+'). If no sign is present, assume the number is positive.Read consecutive digits until a non-digit character appears or the string ends.
Ignore leading zeros; they do not affect the number.
If no digits are found, return
0.If the number is greater than
2147483647, return2147483647.If the number is smaller than
-2147483648, return-2147483648.Otherwise, return the number as it is.
Example 1
Input: s = " -12345"
Output: -12345
Explanation: Skip the leading space, read the negative sign, and convert the digits 12345. Applying the sign gives -12345.
Example 2
Input: s = "4193 with words"
Output: 4193
Explanation: Read the digits 4193. The next character is a space, so conversion stops and returns 4193.
Approach
The main idea is to convert the string into an integer by reading its characters one at a time. Since a valid number may start with spaces or an optional sign, these characters must be handled before processing the digits. Once digit reading begins, each digit contributes to building the final number, and the process stops when a non-digit character is found.
The number is built by multiplying the current result by 10 and adding the new digit. Multiplication by 10 shifts the existing digits one place to the left, making room for the next digit. For example, if the current result is 12 and the next digit is 3, the updated result becomes 12 × 10 + 3 = 123. Leading zeros are handled naturally because they do not change the result.
The sign is tracked separately and applied to determine whether the final value is positive or negative. Since a 32-bit signed integer has a limited range, the result is checked against its minimum and maximum limits during conversion. If the value goes beyond either limit, the corresponding boundary value is returned.
Algorithm
Initialize the index, result, and default positive sign.
Advance the index past all leading space characters.
Read one optional
'+'or'-', record its sign, and advance the index.While the current character is a digit, convert it to its numeric value and update
result = result * 10 + digit.After each update, return
2147483647if the signed result reaches or exceeds the upper limit, or-2147483648if it reaches or falls below the lower limit.Stop at the first non-digit or the end of the string, then return the signed result. If no digits were read, the result remains
0.
Dry Run
String to Integer (atoi)
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to convert a string to a integer int myAtoi(string input) { int i = 0; int n = input.size(); // long long has room for one more digit before the limit check. long long result = 0; // Skip only leading spaces. // Checking i < n also handles empty strings and strings of spaces. while (i < n && input[i] == ' ') { ++i; } // Read at most one sign. Without a sign, keep the number positive. int sign = 1; if (i < n && (input[i] == '+' || input[i] == '-')) { if (input[i] == '-') { sign = -1; } ++i; } // Stop at the end or the first character outside '0' to '9'. while (i < n && input[i] >= '0' && input[i] <= '9') { // Subtracting '0' turns a digit character into its number. int digit = input[i] - '0'; // Move the existing digits one place left, then add this digit. result = result * 10 + digit; ++i; // Check after every digit and return a limit immediately. // This prevents a long input from building a huge number. long long signedValue = sign * result; if (signedValue >= INT_MAX) { return INT_MAX; } if (signedValue <= INT_MIN) { return INT_MIN; } } // The checks above ensure the answer fits in int. // If no digits were read, result is still zero. return sign * result; }};// Driver codeint main() { string input = " -12345"; Solution solution; cout << solution.myAtoi(input) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(N), where N is the length of the string. We go through the string once, checking each character.
Space Complexity: O(1), as we don't use any extra space apart from a few variables.
Interview follow-up Questions
For s = " - 123", the answer is 0. After reading the sign, the next character must be a digit. The function stops at the space and does not search for digits later.
Be the first to add a comment.