Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Strings

String to Integer (atoi)

Medium · Strings · Asked at Amazon, Microsoft, Meta, Bloomberg, Goldman Sachs

Convert the line to a 32-bit signed integer, exactly like this:

  1. Skip leading spaces.
  2. Read an optional + or - sign.
  3. Read digits until a non-digit or the end. Ignore everything after that.
  4. If no digits were read, the result is 0.
  5. Clamp the result to the range [-2^31, 2^31 − 1].

Input

A single line (it may start with spaces and may contain letters, digits, spaces, +, - and .).

Output

The resulting integer.

Constraints

Check for overflow before it happens, or accumulate in a 64-bit number and stop early once it exceeds the range.

Example 1

Input

42

Output

42

Example 2

Input

   -042abc

Output

-42

Hints

  1. Follow the steps in order with an index: skip spaces, read one optional sign, then read digits.
  2. Accumulate in a 64-bit number and clamp as soon as the value passes 2^31 — otherwise a long digit string overflows even 64 bits.

Approach

Read the whole line (it can start with spaces). Move an index past the spaces; if the next character is + or −, remember the sign and step over it. Then, while the character is a digit, do value = value·10 + digit and stop growing once value > 2^31 (clamp). Finally apply the sign and clamp to [−2^31, 2^31 − 1]. Anything after the digits is ignored.

Complexity: O(n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    getline(cin, s);
    size_t i = 0;
    while (i < s.size() && s[i] == ' ') i++;
    int sign = 1;
    if (i < s.size() && (s[i] == '+' || s[i] == '-')) {
        if (s[i] == '-') sign = -1;
        i++;
    }
    long long v = 0;
    while (i < s.size() && isdigit((unsigned char)s[i])) {
        v = v * 10 + (s[i] - '0');
        if (v > 2147483648LL) v = 2147483648LL;
        i++;
    }
    v *= sign;
    v = max(-2147483648LL, min(2147483647LL, v));
    cout << v << "\n";
    return 0;
}

Python solution

import sys

s = sys.stdin.readline().rstrip("\n")
i, sign, v = 0, 1, 0
while i < len(s) and s[i] == " ":
    i += 1
if i < len(s) and s[i] in "+-":
    sign = -1 if s[i] == "-" else 1
    i += 1
while i < len(s) and s[i].isdigit():
    v = min(v * 10 + int(s[i]), 2**31)
    i += 1
print(max(-(2**31), min(2**31 - 1, sign * v)))

Java solution

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        String s = new BufferedReader(new InputStreamReader(System.in)).readLine();
        if (s == null) s = "";
        int i = 0, sign = 1;
        while (i < s.length() && s.charAt(i) == ' ') i++;
        if (i < s.length() && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
            if (s.charAt(i) == '-') sign = -1;
            i++;
        }
        long v = 0;
        while (i < s.length() && Character.isDigit(s.charAt(i))) {
            v = Math.min(v * 10 + (s.charAt(i) - '0'), 2147483648L);
            i++;
        }
        v *= sign;
        v = Math.max(-2147483648L, Math.min(2147483647L, v));
        System.out.println(v);
    }
}

Solve String to Integer (atoi) online · All practice problems