8. String to Integer (atoi)

String to Integer (atoi)

Problem Description

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

 

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

 

Constraints:

• -231 <= x <= 231 - 1

Idea:

From the problem statement and examples, it is clear that we only want to convert those strings which start either from <whitespace>, -, + or numbers 0,1,2,3,4,5,6,7,8,9 and we also don’t care about the non-number characters after the number characters.

Approach

This is a very straightforward problem that can be easily solved with the following steps -

Check if the string is null or empty string. If it is, return 0.

Remove all the leading whitespaces from the given string (if any).

If the string has - or + character at the start, we will keep it stored in a boolean flag.

Loop for each character in the remaining string if and only if they are from the set [0,1,2,3,4,5,6,7,8,9].

Store the result after each iteration in a variable number.

Check if the resultant number is less than -231 or more than 231 - 1 and return the result accordingly.

Else return the calculated number as result.

And thattsss it!!! Easy peasy, right? 😄

Let`s code it!

var myAtoi = function (str) {
    // Base condition
    if (!str) {
        return 0;
    }
    // MAX and MIN values for integers
    const INT_MAX = 2147483647;
    const INT_MIN = -2147483648;
    // Trimmed string
    str = str.trim();
    // Counter
    let i = 0;
    // Flag to indicate if the number is negative
    const isNegative = str[0] === '-';
    // Flag to indicate if the number is positive
    const isPositive = str[0] === '+';
    if (isNegative) {
        i++;
    } else if (isPositive) {
        i++;
    }
    // This will store the converted number
    let number = 0;
    // Loop for each numeric character in the string iff numeric characters are leading
    // characters in the string
    while (i < str.length && str[i] >= '0' && str[i] <= '9') {
        number = number * 10 + (str[i] - '0');
        i++;
    }
    // Give back the sign to the converted number
    number = isNegative ? -number : number;
    if (number < INT_MIN) {
        return INT_MIN;
    }
    if (number > INT_MAX) {
        return INT_MAX;
    }
    return number;
};

Time Complexity

Since we are going through the entire number digit by digit, the time complexity should be O(log10n). The reason behind log10 is that we are dealing with integers which are base 10.

Space Complexity

We are not using any data structure for interim operations, therefore, the space complexity is O(1).

Solution :p Just another way to write 

/**
 * @param {string} s
 * @return {number}
 */
var myAtoi = function(s) {
  const len = s.length;
  let max = 2147483647;
  let min = -2147483648;
  let numberMatch = /^[\d ()+-]+$/;

  for (let i = 0, j = i; i < len; i++) {
    let current = s[i];

    if (current != " " && !current.match(numberMatch)) {
        return 0;
    } else if (current != " " && current.match(numberMatch)) {
      let result = "";

      while (j < len && current.match(numberMatch)) {
        result += s[j];
        j++;
      }
      let output = parseInt(result);
      if (isNaN(output)) return 0;
      else if (output > max) return max;
      else if (output < min) return min;
      else return output;
    }
  }
  return 0;
};

Solution :p Just another way to write 

/**
 * @param {string} s
 * @return {number}
 */
var myAtoi = function(s) {
  let i = 0;
  let sign = 1;
  let res = 0;
  let len = s.length;
  let INT_MAX = 2147483647;
  let INT_MIN = - INT_MAX - 1;

  // skip all space
  while (s[i] === ' ') i++;

  // check sign
  if (s[i] === '+' || s[i] === '-') {
    sign = s[i] === '+' ? 1 : -1;
    i++;
  }

  while (s[i] >= '0' && s[i] <= '9') {
    res = (res * 10) + (s[i] - 0);
    if (sign === 1 && res > INT_MAX) return INT_MAX;
    if (sign === -1 && res > INT_MAX + 1) return INT_MIN;
    i++;
  }

  return res * sign;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #8. String to Integer (atoi)

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!