Learn how to create your custom function just like ATOI to convert a string to integer without using any internal methods.
Example
Input: "-123" "123" Output: -123 123
We are going to see the both iterative and recursive solution for this.
Iteratively convert the string to integer (ATOI)
To convert any string to integer we need to handle four corner cases.
- Invalid input.
- White spaces (leading as well as trailing).
- Sign of the number (negative or positive).
- Overflow (in case the number is exceeding the limit).
We will have to come up with a solution by keeping all theses cases in the mind.
- We first use a variable to track the leading white spaces because after that the number will start.
- Then check if the first character is a number or sign. If it is a sign then store the appropriate value based on the sign type.
1
for positive and-1
for negative. - To convert a string to the number we use its ASCII value difference of the current character with
'0'
character and then keep on adding that to the previous sum multiplied by 10. - In each call check if the formed number is exceeding the limit or not. If it exceeding then based on the sign that is either number is positive or negative return the max limit of it.
- At the end return the new number multiplied by the sign value.
const iterativeATOI = (str) => { let sign = 1; base = 0; i = 0; //Ignore the leading white spaces while(str[i] === ''){ i++; } // Decide sign of number if (str[i] == '-' || str[i] == '+') { sign = 1 - 2 * (str[i++] == '-' ? 1 : 0); } // Checking for valid input while (i < str.length && str[i] >= '0' && str[i] <= '9') { // Handling overflow test case if (base > Number.MAX_VALUE / 10 || (base == Number.MAX_VALUE / 10 && str[i] - '0' > 7)) { if (sign == 1) { return Integer.MAX_VALUE; } else{ return Integer.MIN_VALUE; } } //For the new number base = 10 * base + (str[i++] - '0'); } //Return the number return base * sign; }
Input: console.log(iterativeATOI("-123")); console.log(iterativeATOI("+123")); console.log(iterativeATOI("/123")); Output: -123 123 0 // for invalid inputs
Time complexity: O(n);
Space complexity: O(1);
Recursive solution to convert string to integer in javascript.
We can easily convert the iterative solution to the recursive one. All we need to do is create an extra function which will recursively call itself to convert the string.
const convert = (sign, str, i, base) => { //Validate input if(i < str.length && str[i] >= '0' && str[i] <= '9'){ // Handling overflow test case if (base > Number.MAX_VALUE / 10 || (base == Number.MAX_VALUE / 10 && str[i] - '0' > 7)) { if (sign == 1) { return Integer.MAX_VALUE; } else{ return Integer.MIN_VALUE; } } //Form the number base = 10 * base + (str[i++] - '0'); //Recur to convert the remaining string return convert(sign, str, i, base); } return base * sign; } const recursiveATOI = (str) => { let sign = 1; base = 0; i = 0; n //Ignore leading white spaces while(str[i] === ''){ i++; } //Decide sign of number if (str[i] == '-' || str[i] == '+') { sign = 1 - 2 * (str[i++] == '-' ? 1 : 0); } //Convert the string to integer return convert(sign, str, i, base); }
Input: console.log(recursiveATOI("-123")); console.log(recursiveATOI("+123")); console.log(recursiveATOI("/123")); Output: -123 123 0 // for invalid inputs
Time complexity: O(n).
Space complexity: O(n) considering the call stack.