Valid Number

Breaking down the original number into chunks of decimal and integers:

• A valid number may or may not have ‘e’ or ‘E’ in it.
• If it does not have ‘e’ or ‘E’, it means the number must be an integer or decimal.
• If it does have ‘e’ or ‘E’ it means we can divide the string into two parts, the string on the left of ‘e’ will be our prefix string, and the string on the right of ‘e’ will be our suffix string. Neither suffix nor prefix can be empty.
• The prefix of the string should be either a decimal or an integer and the suffix of the string should be an integer.

Now to check if a number is an integer or not:

• The integer may start with a sign ‘+’ or ‘-’, excluding the sign there should be at least one digit.
• Check if all the remaining characters are digits only, if they are then the number is an integer.
   

Now to check if a number is a decimal or not:

• A decimal may start with the sign ‘+’ or ‘-’.
• A decimal must have ‘.’ in it. If it doesn’t then the number isn’t a decimal.
• If it does have ..’ it means we can divide the string into two parts, the string on the left of ‘.’ will be our prefix string and the string on the right of ‘.’ will be our suffix string. Both suffix and prefix cannot be empty at the same time.
• If both prefix and suffix are integers then the number is a decimal else it is not.
   

Algorithm:

• Create a variable ‘pos’, which stores the position of ‘e’ or ‘E’ in the original string. Also, create a boolean variable ‘valid’ which is true if the number is a valid number else it stores false.
• If ‘e’ or ‘E’ does not exist in the string then set ‘valid’= isDecimal(s) or isInteger(s), i.e. ‘valid’ will be true if the string ‘s’ is decimal or an integer.
  isInteger(s) returns true if the string ‘s’ is an integer, similarly isDeciaml(s) returns true if ‘s’ is a decimal.
• If ‘e’ or ‘E’ exists, then divide string ‘s’ in two parts ‘prefix’ and ‘suffix’. Left part of the string from ‘e’ and right part of the string from ‘e’
• If either of ‘prefix’ and ‘suffix’ is empty, set ‘valid’ = false.
• Else set boolean variable

valid = ( isDecimal(prefix) or isInteger(prefix) ) and isInteger(suffix)        

• If valid is true, then return “Valid” else return “Invalid”.
   

Implementing isInteger(s):

• The integer may start with a sign ‘+’ or ‘-’, excluding the sign there should be at least one digit.
• Check if all the remaining characters are digits only, if they are then the number is an integer.
   

Implementing isDecimal(s):
 

• A decimal may start with the sign ‘+’ or ‘-’.
• Create a variable ‘pos’, which stores the position of ‘.’ in the string.
• If ‘.’ does not exist in the string then return “false”, which means that the string ’s’ is not a decimal.
• If ‘.’ exists, then divide string ‘s’ into two parts ‘prefix’ and ‘suffix’. Left part of the string from ‘.’ and right part of the string from ‘.’
• If ‘prefix’ and ‘suffix’ both are empty then return ‘false’;
• Else if both ‘prefix’ and ‘suffix’ only have integers return ‘true’, else return ‘false’.

O(N),  where N is the length of the string

In the worst case, we will end up dividing the strings into different strings of length 1, there will be ‘N’ such strings, thus time complexity will be O(N)
 

O(N),  where N is the length of the string

We are creating prefix and suffix strings which can be of length O(N)