Implement Atoi Function

Hard
0/120
Average time to solve is 10m
profile
Contributed by
111 upvotes
Asked in companies
AmazonAdobeMorgan Stanley

Problem statement

You are given a string ‘s’ of length 'n'.


Implement the atoi(string s) function, which converts a given string into a 32-bit signed integer, following similar principles as the atoi function in C/C++.


Here's the step-by-step algorithm for myAtoi(string s):


1. Discard any leading whitespaces.


2. If the next character (if not at the end of the string) is '-' or '+', consider it to determine the sign of the result. If neither is present, assume the result is positive.


3. Read and accumulate digits until a non-digit character is encountered or the end of the input is reached.


4. Convert the collected digits into an integer (e.g., "123" becomes 123, "0032" becomes 32). If no digits were read, the integer is 0. Adjust the sign as needed (as determined in step 2).


5. If the integer falls outside the range of a 32-bit signed integer [-2^31, 2^31 - 1], constrain it to stay within the range. For instance, if the integer is less than -2^31, set it to -2^31; if it's greater than 2^31 - 1, set it to 2^31 - 1.


6. Return the resulting integer.


Note : 
1. Only the space character ' ' is treated as a whitespace.

2. All characters other than leading whitespace or digits are considered.


Example: 
Input: 45rohit12

Output: 45

Explanation: 
Leading Whitespace: Leading whitespace characters (" ") are ignored.

Numeric Portion: The numeric portion starts with the digit "4".

Reading Numeric Characters: The algorithm reads "4" and "5" to form "45".

End of Numeric Portion: The numeric portion ends at "r", non-numeric characters are skipped.

Parsing Result: "45" is parsed into the integer value 45, the final result.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The only line of the test case contains the string ‘s’.
Output format : 
The output contains the integer formed by the given string.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.


Sample Input 1 :
-546+er
Sample Output 1 :
-546
Explanation For Sample Input 1:
Leading Whitespace: Leading whitespace characters (" ") are ignored.

Sign Detection: The "-" sign indicates a negative result.

Numeric Portion: The numeric portion begins with the digit "5".

Reading Numeric Characters: The algorithm reads "5", "4", and "6" to form "546".

End of Numeric Portion: The numeric portion ends at "+".

Parsing Result: "546" is parsed into the integer value 546. Due to the negative sign, the final result is -546.
Sample Input 2 :
-ban23
Sample Output 2 :
0
Constraints:
0 <= n <= 200

's' consists of English letters (lower-case and upper-case), digits (0-9), '  ', '+', '-', and '.'.
Hint

Try to solve the problem Iteratively. 

Approaches (1)
Iterative Approach

Approach:
The approach involves parsing a string to convert it into a 32-bit signed integer. The algorithm starts by skipping leading whitespaces. It detects positive or negative signs and accumulates the numeric portion of the string. By converting characters to integers, it forms the integer value. The approach handles cases of negative signs, sign clashes, and integer range limits. The result is returned as the final output. 
 

Algorithm :

FUNCTION createAtoi(s: string) -> 

  • Initialise i = 0
  • n = length of s
  • WHILE s[i] is whitespace
    • i++
  • Initialise positive = 0
  • Initialise negative = 0
  • IF s[i] is '+'
    • positive++
    • i++
  • ELSE IF s[i] is '-'
    • negative++
    • i++
  • Initialise ans = 0
  • WHILE i < n AND s[i] is a digit (0-9)
    • ans = ans * 10 + (s[i] - '0')
    • i++
  • IF negative > 0
  • ans = -1*ans
  • IF positive > 0 AND negative > 0
    • RETURN 0
  • IF ans > INT_MAX
    • ans = INT_MAX
  • ELSE IF ans < INT_MIN
    • ans = INT_MIN
  • RETURN ans
Time Complexity

O(N), where ‘N’ denotes the length of the string.

 

We traverse the string once.

 

Therefore the overall time complexity will be O(N).

Space Complexity

O(1)

 

We are not using any extra space.

 

Therefore overall space complexity will be O(1).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Implement Atoi Function
Full screen
Console