Is the Number Valid

editor-page-cover

Problem Statement

Given an input string, determine if it makes a valid number or not. For simplicity, assume that white spaces are not present in the input.

4.325 is a valid number.
1.1.1 is NOT a valid number.
222 is a valid number.
22. is NOT a valid number.
0.1 is a valid number.
22.22. is NOT a valid number.
1. is NOT a valid number.


Hint

  • Use state machine

Try it yourself

bool is_number_valid(string s) {
//TODO: Write - Your - Code
return false;
}

Solution

enum STATE { START, INTEGER, DECIMAL, UNKNOWN, AFTER_DECIMAL};
STATE get_next_state(STATE current_state, char ch) {
switch(current_state) {
case START:
case INTEGER: {
if (ch == '.') {
return DECIMAL;
} else if (ch >= '0' && ch <= '9') {
return INTEGER;
} else {
return UNKNOWN;
}
break;
}
case DECIMAL:
if (ch >= '0' && ch <= '9') {
return AFTER_DECIMAL;
} else {
return UNKNOWN;
}
break;
case AFTER_DECIMAL:
if (ch >= '0' && ch <= '9') {
return AFTER_DECIMAL;
} else {
return UNKNOWN;
}
break;
case UNKNOWN:
return UNKNOWN;
}
return UNKNOWN;
}
bool is_number_valid(const string s) {
int i = 0;
if (s[i] == '+' || s[i] == '-') {
i++;
}
STATE current_state = START;
while (s[i] != '\0') {
current_state = get_next_state(current_state, s[i]);
if (current_state == UNKNOWN) {
return false;
}
i++;
}
if (current_state == DECIMAL)
return false;
return true;
}
void test(const string s, bool expected) {
bool is_valid = is_number_valid(s);
if (is_valid) {
cout << s << " is valid." << endl;
} else {
cout << s << " is not valid." << endl;
}
}
int main(int argc, char* argv[]) {
test("4.325", true);
test("4.325a", false);
test("x4.325", false);
test("4.32.5", false);
test("4325", true);
test("1.", false);
test("1.1.", false);
test("1.1.1", false);
test("1.1.1.", false);
test("+1.1.", false);
test("+1.1", true);
test("-1.1.", false);
test("-1.1", true);
test("", true);
}

Solution Explanation

Runtime Complexity

Linear, O(n).

Memory Complexity

Constant, O(1).


Solution Breakdown

We’ll use the state machine below to check if a number is valid or not. The initial state is ‘Start’. We’ll process each character to identify the next state. The input string is not a valid number if we reach an UNKNOWN state at any point or if it ends in a DECIMAL.

widget

We are not looking at the sign (+ or -) at the start of a number in the state machine. If there is a sign at the start of the input string, we start processing the string for the state machine after that sign character.

Practice problems like this and many more by checking out our Grokking the Coding Interview: Patterns for Coding Questions course!