Add One to a Number

The question is as following:

We're given a non-negative number represented in the form of an array and we have to add 1 to that number.

The number is stored in such a way that the most significant digit is the starting element of the array.

Eg:  A vector is given as [ 9, 9, 9] then the answer should be [1,0,0,0].

We have to return the answer in the form of an array also.

The first thing which comes in our mind is to simply convert the array to a number then add 1 and again convert into an array. This how so ever is not going to work as the array could contain thousands of number and you can't store such a big number.

The idea is to use the basic approach of how we would really add 1 to a number, on paper.

By adding and maintaining the carry.

As we start adding from end, the first step is to reverse the array then add 1 and the again reverse the array.

We also have to take care where "0" comes as the most significant bit. as [0,1,3,4] would not be a proper answer.

The following code does the same:

vector<int> solve(vector<int> &A) {



reverse(A.begin(), A.end());      //reversing the array



vector<int> s;

int carry =1;                      // Intializing carry as 1
for(int i=0;i<A.size();i++)

{


 int sum  = A[i] + carry;    //   adding carry to the element

 s.push_back(sum%10);              // pushing only the last digit in the array

 carry = sum/10;                  // maintaining carry
}


if(carry){                         // if carry is still left after adding

s.push_back(carry);          // i.e when the no. of digits are increased after adding
}                                       // 999 + 1 = 1000


       

while(s[s.size()-1]==0  && s.size()>1)
{


s.pop_back();        // removing 0 if present as the most significant bit

}      // which is the least significant bit now as array is reversed. 

reverse(s.begin(),s.end());  // Again reversing the array
return s;


}