String to Integer (atoi)

medium Strings

Problem

Convert the first line to an integer like a simple parser: skip leading spaces, read an optional + or -, then read digits until the first non-digit. If there are no digits, the answer is 0. Clamp the result to the 32-bit range -2147483648 to 2147483647. Print the number.

Constraints

  • 0 <= length <= 200

Examples

Input

   -42

Output

-42

Input

4193 with words

Output

4193

Solutions

Best approachTime O(n)Space O(1)

This is the classic hand-written parser. Integer.parseInt would throw on text such as 4193 with words, so we read the digits ourselves and clamp the result.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Parse an integer.
 * Input   : One line, may be empty.
 * Output  : The parsed number.
 * Approach: Parse by hand.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static long solve(String[] lines) {
        // Step 1: Take the first line. An empty input has no line at all.
        String text = lines.length > 0 ? lines[0] : "";
        int index = 0;
        // Step 2: Skip the leading spaces.
        while (index < text.length() && text.charAt(index) == ' ') {
            index++;
        }
        // Step 3: Read an optional sign.
        long sign = 1;
        if (index < text.length() && (text.charAt(index) == '+' || text.charAt(index) == '-')) {
            sign = text.charAt(index) == '-' ? -1 : 1;
            index++;
        }
        // Step 4: Read digits. Stop early when the value is already too big, so a long cannot overflow.
        long value = 0;
        while (index < text.length() && Character.isDigit(text.charAt(index)) && value <= 3000000000L) {
            value = value * 10 + (text.charAt(index) - '0');
            index++;
        }
        // Step 5: Apply the sign and clamp to the 32-bit range.
        value *= sign;
        return Math.max(-2147483648L, Math.min(2147483647L, value));
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            all.add(scanner.nextLine());
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(solve(lines));
    }
}
Hints (1)
  1. Why stop reading digits early in Java?