DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

String to Integer (atoi)

mediumStrings Must-doMicrosoft SRE

Problem statement

Write myAtoi(s), which reads a 32-bit signed integer from the start of a string, the way C's atoi does. Apply these steps in order:

  1. Skip any leading space characters (' ').
  2. If the next character is + or -, it sets the sign. At most one sign is read.
  3. Read digits until the first non-digit character or the end of the string. Leading zeros are fine. If there are no digits at all, the result is 0.
  4. If the number is outside the 32-bit range [-2^31, 2^31 - 1], clamp it to the nearest end of that range.

Everything after the digits is ignored. Return the integer.

Examples

Example 1

Input: s = " -0042abc"

Output: -42

Explanation: Skip the spaces, read the minus sign, read "0042", then stop at "a".

Example 2

Input: s = "9876543210"

Output: 2147483647

Explanation: The value is larger than 2^31 - 1, so it is clamped to 2147483647.

Hints

Approach

Parse in one pass and never let the running value leave the 32-bit range. Before adding each digit d, check whether result * 10 + d would exceed 2^31 - 1. That happens exactly when result > (MAX - d) / 10 using integer division. If it would, return the clamped value right away.

  1. Skip spaces. Read an optional sign.
  2. For each digit d: if result > (MAX - d) // 10, return MAX for a positive sign or MIN for a negative one. Otherwise result = result * 10 + d.
  3. Return sign * result.

The negative side needs no special case: -2^31 is one more than MAX in magnitude, so any magnitude that passes MAX means clamping to MIN for negatives, and a magnitude of exactly 2^31 also clamps to MIN, which is correct.

ComplexityTime O(n)Space O(1)
Python
class Solution:
def myAtoi(self, s: str) -> int:
INT_MAX, INT_MIN = 2**31 - 1, -2**31
i, n = 0, len(s)
while i < n and s[i] == " ":
i += 1
sign = 1
if i < n and s[i] in "+-":
sign = -1 if s[i] == "-" else 1
i += 1
result = 0
while i < n and s[i] in "0123456789":
d = ord(s[i]) - 48
if result > (INT_MAX - d) // 10: # result * 10 + d would overflow
return INT_MAX if sign == 1 else INT_MIN
result = result * 10 + d
i += 1
return sign * result

Follow-up questions

  • Extend it to 64-bit integers, then to accept an optional 0x hexadecimal prefix.
  • Parse sizes such as "512K", "20M" or "3G" into a byte count.

Frequently asked questions

Python's str.isdigit() and Java's Character.isDigit() accept non-ASCII digits such as Arabic-Indic numerals or superscripts. The task only means 0 to 9, so an explicit check avoids surprising matches.

Only one sign character is read. After +, the next character - is not a digit, so no digits are found and the result is 0.

Parsing numbers out of messy text is everyday tooling work: reading a port or a byte count from a config line, a status code from a log, or a value from command output. The overflow check is the same care you need when summing counters that can exceed 32 bits.