DEV Community

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

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...
Collapse
 
lionelrowe profile image
lionel-rowe • Edited

Troll answer (JS):

const atoi = parseInt
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode
Collapse
 
urielbitton profile image
Uriel Bitton

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

function atoi(str) {
return +str
}

Collapse
 
lionelrowe profile image
lionel-rowe

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

Thread Thread
 
momodev profile image
Santiago G. Marín

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

Thread Thread
 
urielbitton profile image
Uriel Bitton

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

Thread Thread
 
momodev profile image
Santiago G. Marín

Not if you only want integers...

Thread Thread
 
lionelrowe profile image
lionel-rowe

@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.

Thread Thread
 
urielbitton profile image
Uriel Bitton

just add .toFixed(0)

Thread Thread
 
urielbitton profile image
Uriel Bitton

just add .toFixed(0) ...

Thread Thread
 
lionelrowe profile image
lionel-rowe

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
Enter fullscreen mode Exit fullscreen mode

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.

Collapse
 
maixuanhan profile image
Han Mai • 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.

Collapse
 
manchicken profile image
Mike Stemle • 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;
}
Enter fullscreen mode Exit fullscreen mode

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.

Collapse
 
lionelrowe profile image
lionel-rowe

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;
Enter fullscreen mode Exit fullscreen mode
Collapse
 
manchicken profile image
Mike Stemle

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

Collapse
 
lionelrowe profile image
lionel-rowe • 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)));
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
joanllenas profile image
Joan Llenas Masó • 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
Enter fullscreen mode Exit fullscreen mode

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

Collapse
 
lionelrowe profile image
lionel-rowe

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" ])
Enter fullscreen mode Exit fullscreen mode
Collapse
 
joanllenas profile image
Joan Llenas Masó

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.

Collapse
 
logicallynerd profile image
logically-nerd • 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;
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
lionelrowe profile image
lionel-rowe

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.

Collapse
 
logicallynerd profile image
logically-nerd

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.

Collapse
 
vsaulis profile image
Vladas Saulis

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

Collapse
 
joanllenas profile image
Joan Llenas Masó

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

Collapse
 
vsaulis profile image
Vladas Saulis • 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.

Thread Thread
 
joanllenas profile image
Joan Llenas Masó

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
Enter fullscreen mode Exit fullscreen mode

Cheers!

Thread Thread
 
vsaulis profile image
Vladas Saulis

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

Collapse
 
tristan_m profile image
Tristan M・トリスタン

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

const stringNum = "12345"
const intNum = +stringNum
Enter fullscreen mode Exit fullscreen mode
Collapse
 
manchicken profile image
Mike Stemle

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

Collapse
 
nasheomirro profile image
Nashe Omirro
npm i atoi-js
Enter fullscreen mode Exit fullscreen mode