Find a missing number in a string -- Amazon

Solution

/*

============================================================================

Author : James Chen

Email : a.james.chen@gmail.com

Description : Find a missing number in a string

Created Date : 23-September-2013

Last Modified : 24-09-2013

============================================================================

*/

#include <iostream>

#include <iomanip>

#include <string>

using namespace std;

bool ExpectedNextNum(string str, int num, int start)

{

if(start + to_string(num).size() > str.size()){

return false;

}

int expected = stoi(str.substr(start, to_string(num).size()));

return (num == expected);

}

int FindMissingNum(string str)

{

int len = str.size();

int i = 1;

int missingNum;

while(i <= len / 2){

int start = i;

int curr = stoi(str.substr(0, i));

bool bOk = true;

while(bOk){

if(bOk = ExpectedNextNum(str, curr + 1, start)){

start += to_string(curr + 1).size();

curr = curr + 1;

}

else if(bOk = ExpectedNextNum(str, curr + 2, start)){

start += to_string(curr + 2).size();

missingNum = curr + 1;

curr = curr + 2;

}

}

if(start == len){

return missingNum;

}

i ++;

}

}

void DoTest(string str)

{

cout << "Input : " << str << endl;

cout << "Output : " << FindMissingNum(str) << endl;

cout << "--------------------------------" << endl;

}

int main(int argc, char* argv[])

{

DoTest("0123456781011");// expect 9

DoTest("012345678911"); // expect 10

DoTest("911"); // expect 10

DoTest("4142434546"); // expect 44

DoTest("99101102103"); // expect 100

DoTest("101112101114"); // expect 101113

return 0;

}

Output

Input : 0123456781011

Output : 9

--------------------------------

Input : 012345678911

Output : 10

--------------------------------

Input : 911

Output : 10

--------------------------------

Input : 4142434546

Output : 44

--------------------------------

Input : 99101102103

Output : 100

--------------------------------

Input : 101112101114

Output : 101113

--------------------------------

Press any key to continue . . .