**The problem**

Problem statement (requires login)

Summary of the statement is:

Given an array of non-negative integers

an integerprogram[],,wantedResultand pseudocode of a peculiar program. This program takesas argument, and reads it through. There’s also a stack initially filled with infinite number of 0’s. Ifprogram[]= 0 it pops topmost two elements from the stack, adds them up, and pushes the sum into the stack, otherwise it pushesprogram[i]into stack. At the end of execution, it pops and prints the top element of the stack.program[i]The trouble is exactly one of

s elements is -1. But the program operates only on non-negative integers. Return the smallest non-negative integer with which -1 can be replaced such that the program’s output isprogram[]‘. If no such non-negative integer exists, return -1 instead.wantedResult

**The idea**

I started with trivial observations like disregarding all values before first 0 except the last two doesn’t change the result, etc. The key idea came out after some more moment’s thought.

The most important thing to note is, *the program’s output is the sum of some positive integers, hence it**s output is bounded to be strictly increasing.* Whenever I observe an *increasing/decreasing* function, *binary search* is the first thing that pops in my mind.

Closer examination reveals that three possible cases may arise as the replacement of -1. They are:

- infinite number of valid choices (
*i.e. in fact,**the value at -1 is never added to the program’s output*) - only one unique choice (
*i.e. the program returns***wantedResult**,*if and only if**-1 is replaced with this value*) - no valid choice at all (
*i.e. the program never outputs*)**wantedResult**whatever we replace -1 with

A check for 0 as -1’s replacement is sufficient to get rid of case 1, and for the rest two a binary search will do. Rushed into coding then.

**Solution**

I ended up with the Following C++ code.

class Suminator { public: int val(vector<int> program, int ln) { int l = 0; vector<int> s; for(int i = 0; i < ln; i++) { if(program[i] == 0) { long long a = 0, b = 0; if(l > 0) { a = s[l - 1]; s.pop_back(); l--; } if(l > 0) { b = s[l - 1]; s.pop_back(); l--; } s.push_back(a + b); l++; } else { s.push_back(program[i]); l++; } } if(l == 0) { return 0; } return s[l - 1]; } int findMissing( vector <int> program, int wantedResult ) { int ln = program.size(); int lb = 0, ub = 1000000010, mid; vector<int> v = program; int ind = 0; for(int i = 0; i < ln; i++) { if(program[i] == -1) { ind = i; break; } } v[ind] = 0; if(val(v, ln) == wantedResult) { return 0; } while(lb < ub) { mid = (lb + ub + 1) >> 1; v[ind] = mid; if(val(v, ln) > wantedResult) { ub = mid - 1; } else { lb = mid; } } v[ind] = lb; if(val(v, ln) == wantedResult) { return lb; } return -1; } };

**Mistake!**

But, this solution got stuck on some case in the system test. I was just too confident about my reasoning. Only mistake I could imagine is overflow, and really it was.

**Correction**

In line 29 of function *val(),* an addition is being performed. As elements of ** program[] **may be as large as , an overflow is possible.

*Changing the function*

*val()’*s return type (line 4) and

*vector<int> s’*s type (line 7) to

*long long*does the correction.