DEV Community

Coding Problem Interview Series: How to Convert a String to Integer (atoi())?

Ben Halpern on July 10, 2023

📣 Calling experienced devs and recent interviewees! Join the "Coding Problem Interview Series" to help code newbies tackle interview questions asse...

Read full post

lionel-rowe • Jul 10 '23 • Edited

Troll answer (JS):

const atoi = parseInt

I think this needs a few self-imposed rules, such as not using any built-in language features or APIs to do the conversion.

function atoi(str) {
    // match 0-1 signs (+ or -), followed by 1 or more ASCII digits
    // formats like "1", "01", "+1", "-1" are allowed
    // formats like "0xff", "1e6", "1.1", " 1 " are rejected
    const matched = str.match(/^([+\-]?)(\d+)$/)

    // `matched` will be `null` if the format requirement wasn't met,
    // so we return Not a Number
    if (!matched) return NaN

    // destructure the capture groups: 0 is discarded (full match)
    const [, sign, digits] = matched

    let total = 0
    // go through the decimal places in reverse:
    // units, tens, hundreds, etc.
    for (const [i, digit] of [...digits].reverse().entries()) {
        // subtract 0x30 from the codepoint, as ASCII digits are
        // located at codepoints 0x30..0x39
        // (i.e. "0" is codepoint 0x30, "1" is 0x31, etc.)
        // multiply by 10 raised to the power of the appropriate
        // decimal place
        total += (digit.codePointAt(0) - 0x30) * 10 ** i
    }

    // multiply by -1 if the sign was negative
    return total * (sign === '-' ? -1 : 1)
}

atoi('42') // 42
atoi('-99') // -99
atoi('+500') // 500
atoi('0001230') // 1230
atoi('1.5') // NaN

Uriel Bitton • Jul 19 '23

lol. let me do all your work in a single line:

function atoi(str) {
return +str
}

lionel-rowe • Jul 19 '23

@urielbitton I still prefer my one-liner const atoi = parseInt, because +str doesn't fulfil the spec (might return a non-integer) 😉

Santiago G. Marín • Jul 19 '23

True, +'...' behaves similar to Number, so it'll convert floats as well.

Uriel Bitton • Jul 19 '23

@lionelrowe + quite literally replaces parseInt in 99% or perhaps 100% of cases in javascript.

Santiago G. Marín • Jul 19 '23

Not if you only want integers...

lionel-rowe • Jul 20 '23

@urielbitton It depends what your use case is. I usually use Number(str) instead of +str as it's more explicit, plus it can be passed as a callback to array functions (['1', '2', '3'].map(Number) => [1, 2, 3]). I usually only use parseInt if I want to parse in a radix other than 10, e.g. parsing hex strings (parseInt('ff', 16) => 255), or if I want the result to be truncated (parseInt('16.9') => 16). And I use parseFloat where I want to ignore a unit at the end, e.g. parseFloat('99.9%') => 99.9.

Uriel Bitton • Jul 23 '23

just add .toFixed(0)

Uriel Bitton • Jul 23 '23

just add .toFixed(0) ...

lionel-rowe • Jul 24 '23

OK, that potentially covers 1 of the 4 use cases I mentioned, but it doesn't even work, as toFixed converts it back to a string...

function doNothing(numStr) {
    const num = +numStr
    const fixed = num.toFixed(0)

    return fixed
}

const numStr = '1'
typeof doNothing(numStr) // 'string'
doNothing(numStr) === numStr // true

Sure, you could re-convert to a number, but at that point you're degrading performance and complicating your code just to avoid using parseInt, a function that already exists natively in the language for that specific purpose.

Han Mai • Jul 10 '23 • Edited

The second answer is somehow same idea with the first answer but then the first one is much cleaner and more efficient in any ways. Solution they are looking for is maybe to parse manually, taking care of the cases, char to integer… very basic.

Mike Stemle • Jul 11 '23 • Edited

int atoi_func(const char* str, size_t len) {
  int aggregator = 0;
  char *ptr = str;

  while (*ptr != '\0' && (ptr - str) < len) {
    int digit = *ptr - '0';
    if (digit > 9 || digit < 0) {
      fprintf(stderr, "«%c» is not a digit.\n", *ptr);
      return -1;
    }

    aggregator += digit * (ptr - str);
  }

  if (*ptr != '\0') {
    fprintf(stderr, "potential overflow detected; no null terminator.\n");
    return -1;
  }

  return aggregator;
}

This was really hard to type in an iPhone, but I am pretty sure this is good, and that it covers the most common foot-guns.

lionel-rowe • Jul 11 '23

Nice! Needs a couple of changes though — the math isn't quite right for summing the digits, and the while loop doesn't terminate as ptr is never incremented:

+ #include <math.h>

-    aggregator += digit * (ptr - str);
+    aggregator += digit * pow(10, len - (ptr - str) - 1);
+    ++ptr;

Mike Stemle • Jul 11 '23

Thanks! I knew there was no way I nailed it first go on my iPhone.

lionel-rowe • Jul 10 '23 • Edited

Rust (be gentle, I'm learning 😅)

use std::error::Error;
use std::fmt;

#[derive(Debug)]
pub enum AtoiError {
    IntegerOverflow,
    ZeroLengthInput,
    InvalidChar(char),
}

impl fmt::Display for AtoiError {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{:?}", self)
    }
}

impl Error for AtoiError {}

pub fn atoi(input: &str) -> Result<i64, AtoiError> {
    use crate::AtoiError::*;

    let mut chars = input.chars();

    // `sign` can be either `Some('+')`, `Some('-')`, or `None`
    let sign = match chars.next() {
        x @ Some('-' | '+') => x,
        Some(_) => None,
        None => return Err(ZeroLengthInput),
    };

    // `chars` iterator is currently at index 1 due to calling `next`
    // in previous expression.
    // If the sign wasn't explicitly specified, then re-start chars
    // iterator from index 0
    if sign.is_none() {
        chars = input.chars();
    }

    let mut total: i64 = 0;

    // Go through the decimal places in reverse:
    // units, tens, hundreds, etc.
    for (i, c) in chars.rev().enumerate() {
        match c {
            // Check if char is a digit
            c if c >= '0' && c <= '9' => {
                // Subtract codepoint of '0' from the char.
                // Multiply by 10 raised to the power of the appropriate
                // decimal place

                total = total
                    .checked_add(
                        (c as i64 - '0' as i64)
                            .checked_mul(10i64.checked_pow(i as u32).ok_or(IntegerOverflow)?)
                            .ok_or(IntegerOverflow)?,
                    )
                    .ok_or(IntegerOverflow)?;
            }
            // Return error result if char is not a digit
            c => return Err(InvalidChar(c)),
        };
    }

    // Multiply by -1 if the sign was negative
    Ok(match sign {
        Some('-') => total * -1,
        _ => total,
    })
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::AtoiError::*;

    #[test]
    fn valid() {
        assert!(matches!(atoi("0"), Ok(0)));
        assert!(matches!(atoi("42"), Ok(42)));
        assert!(matches!(atoi("-99"), Ok(-99)));
        assert!(matches!(atoi("+500"), Ok(500)));
        assert!(matches!(atoi("0001230"), Ok(1230)));
    }

    #[test]
    fn invalid() {
        assert!(matches!(atoi(""), Err(ZeroLengthInput)));
        assert!(matches!(atoi("1.5"), Err(InvalidChar('.'))));
        assert!(matches!(atoi("1-2"), Err(InvalidChar('-'))));
        assert!(matches!(atoi("1+3"), Err(InvalidChar('+'))));
        assert!(matches!(atoi("999999999999999999999"), Err(IntegerOverflow)));
    }
}

Joan Llenas Masó • Jul 12 '23 • Edited

Elm + Parser combinators:

You begin with the Integer data structure.

The intP parser is a recipe of how you can generate an Integer instance from a raw string, step by step.

Once you have filled all the holes of the data structure, you can then process it and generate the integer value (with the applySign function).

The atoi function wraps the execution of the parser and returns the Maybe Int value.

import Parser as P exposing ((|.), (|=), Parser)


type Sign
    = Positive
    | Negative


type Integer
    = Integer Sign String


applySign : Integer -> Maybe Int
applySign (Integer sign digits) =
    case ( sign, String.toInt digits ) of
        ( Positive, Just n ) ->
            Just n

        ( Negative, Just n ) ->
            Just (-1 * n)

        _ ->
            Nothing


intP : Parser Int
intP =
    P.succeed Integer
        |= P.oneOf
            [ P.symbol "+" |> P.map (always Positive)
            , P.symbol "-" |> P.map (always Negative)
            , P.succeed Positive
            ]
        |= (P.chompWhile Char.isDigit |> P.getChompedString)
        |. P.end
        |> P.andThen
            (\integer ->
                case applySign integer of
                    Just n ->
                        P.succeed n

                    Nothing ->
                        P.problem "applySign failed"
            )


atoi : String -> Maybe Int
atoi input =
    P.run intP input |> Result.toMaybe

atoi "1" -- Just 1
atoi "45" -- Just 45
atoi "-45" -- Just -45
atoi "" -- Nothing
atoi "--335" -- Nothing
atoi "-3-42" -- Nothing

This approach is closer to intermediate/advanced than to newbies, but this is how parsing is done in a functional style.

If you want to play with the exercise: ellie-app.com/nm6g8LCw37za1

lionel-rowe • Jul 13 '23

I love reading Elm code even though I find it hard to understand, it's kinda brain-bending in a good way!

I noticed you're using String.toInt though, so you could replace the whole atoi implementation with that, as it already handles + and -:

module Main exposing (main)
import Html exposing (Html)

atoi = String.toInt

parse : String -> Html msg
parse s =
    atoi s
        |> Maybe.map String.fromInt
        |> Maybe.withDefault ("'" ++ s ++ "' is not a number")
        |> (\res -> Html.li [] [ Html.text res ])

main =
    Html.ul [] (List.map parse [ "0", "1", "45", "-45", "", "--335", "3abc" ])

Joan Llenas Masó • Jul 13 '23

You are absolutely right! String.toInt already does the job. Wouldn't that be considered cheating during a job interview, though? :)

Parser combinators are an extra brain-bending feature within the language. But it is so powerful that it's worth learning if you want to parse stuff and RegEx falls too short for the job.

logically-nerd • Jul 12 '23 • Edited

JAVA
(still learning, so forgive my not so neat code😅)

class Solution {
    public int myAtoi(String s) {
        double num = 0;
        boolean neg=false,numFound=false,space=false;
        int charCount=0;
        for (char ch : s.toCharArray()) {
            if(charCount>=2){
                break;
            }
            if(charCount>0 && space){
                break;
            }
            if (ch >= '0' && ch <= '9') {
                numFound=true;
                num = ((int) ch - 48) + num * 10;
            }
            else if(!numFound&&ch=='-'){
                space=false;
                neg=true;
                charCount++;
            }
            else if(!numFound&&ch=='+'){
                space=false;
                charCount++;
            }
            else if(!numFound&&ch==' '){
                space=true;
                continue;
            }
            else if(!numFound&&ch=='.'){
                break;
            }
            else{
                break;
            }
        }
        if(neg)
            return (int)(0-num);
        return (int)num;
    }
}

lionel-rowe • Jul 13 '23

Works perfectly, at least for well-formed input. For malformed input, Solution#.myAtoi('abc123') gives 0, and Solution#.myAtoi('123abc') gives 123, which is a reasonable thing to do if you want parsing to be lenient (JS's parseInt works similarly, except it returns NaN instead of 0 where the input begins with an unparseable char).

I don't think it makes much sense to have num be a double and then cast it to an int when returning it, though. To improve performance if nothing else, it'd be better to declare it as an int, then you can remove all the type casts.

The only possible drawback is that it changes the behavior for values that overflow the max int value: with purely int types, you get wrapping (2147483647 + 1 = -2147483648), whereas if using a double internally, you get saturation (2147483647 + 1 = 2147483647). I don't think either one is strictly more/less correct than the other, though.

logically-nerd • Jul 13 '23

Hey lionel,
I just copied the copied that I wrote for the same questions in leetcode.😅
My code is logically designed based on its demand and test cases.

Vladas Saulis • Jul 10 '23

var s = "2345";
var result = 1*s;

Joan Llenas Masó • Jul 13 '23

Works most of the time, but there are a few edge cases:
"", " " are invalid inputs yet they return 0

Vladas Saulis • Jul 13 '23 • Edited

There is a lot of invalid inputs ("aaa", "baa", etc). You must know what you do.
But "" and " " are VALID inputs, because it returns valid answer - 0.

Joan Llenas Masó • Jul 13 '23

Hey Vladas, sorry I wasn't clear enough in my response.
Let me illustrate my point:

1 * "3" // 3 <-- correct
1 * "a" // NaN <-- correct
1 * "" // 0 <-- incorrect, should have been NaN
1 * " " // 0 <-- incorrect, should have been NaN

Cheers!

Vladas Saulis • Jul 13 '23

It must be an internal parser which just skips initial blanks, and it's initialized to 0.
I would program exactly the same.

Tristan M・ﾄリスタン • Jul 10 '23

JS / TS Shorthand I only discovered more recently than I'm willing to admit

const stringNum = "12345"
const intNum = +stringNum

Mike Stemle • Jul 11 '23

Perl had something that some referred to as the Venus operator, 0+. Very clever stuff.

Nashe Omirro • Jul 11 '23

npm i atoi-js