Problem Statement

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