About usWhy usInstructorsReviewsCostFAQContactBlogGet Started

Implement String To Integer Function

Problem Statement


Implement String To Integer Function


Given a string s, which may contain numeric characters as well as non-numeric characters, you have to extract first integer out of it.


Rules are:

● Left most contiguous digits will form the integer, everything after that should be ignored. ("ik45 2" -> 45, because 45 and 2 are not contiguous.)

● Sign ('+' or '-') will be effective only if it is just before the integer. If no sign just before the integer then '+' is applied by default. ("42" -> 42, because '+' is applied by default. "ik-42" -> -42, because - appears just before 42. "ik- 42" -> 42 because there is a space before 42.) 

● If there is no number present then return 0. ("Cpp" -> 0.)


Input/Output Format For The Function:


Input Format:


There is only one argument denoting string s.


Output Format:


Return first integer no, extracted from given string s. 


Input/Output Format For The Custom Input:


Input Format:


The first and only line of input should contain a string s, denoting an input string.


If s = “  ik  +-4 289 ik”, then input should be:


  ik  +-4 289 ik


Output Format:


There will be one line of output, containing an integer no, denoting the result returned by solution function.

For input s = “  ik  +-4 289 ik”, output will be:

-4


Constraints:

● 1 <= |s| <= 10^5

● s may contain numeric characters as well as non-numeric characters. 

● If number is present then it is guaranteed that it will fit in integer. (No need to think about integer overflow.)

● Solution with linear time complexity and constant space is expected.


Sample Test Cases:


Sample Test Case 1:


Sample Input 1:

"  ik  +-4 289 ik"

Sample Output 1:

 -4


Sample Test Case 2:


Sample Input 2:

"- +  -  5ik  "


Sample Output 2:

5


Sample Test Case 3:


Sample Input 3:

"i-k42ki59"


Sample Output 3:

42


Notes:

This problem has many variants. Small change in any condition will change the solution. So clarify any doubts before presenting your solution in interviews.  


Solutions


Have a look at the solution provided by us.


Time Complexity:


O(|s|).

As in worst case (when integer is not present in the string or present at the end of string) we need to iterate over the whole string. 


Auxiliary Space Used:

O(1).


Space Complexity:


O(|s|).

As space complexity includes the input size also.

Note that generally we use Auxiliary Space Used = Space Complexity, but there is a different. Auxiliary space does not count the input size but space complexity does.