We have a pretty simple problem for today’s Leetcode July Challenge. The problem presents us with an array of single digit, decimal integers that, taken together, represent an integer number with the 0-index being the most significant digit. We are to take that array-integer and add one to it. Sound pretty easy, so let’s look at the three likely input scenarios. The first case is that for each integer $i$, $\;0 \leq i < 9$.

Input: $\;[1,2,3] + 1$

Output: $\;[1,2,4]$

The next case to consider is when there are one or more 9’s from the least significant digit side.

Input: $\;[1,9,9] + 1$

Output: $\;[2,0,0]$

The one sort of quirky case is if we are given an array containing only 9’s.

Input: $\;[9,9,9] + 1$

Output: $\;[1,0,0,0]$

Note: One temptation to avoid here would be trying to convert the entire array to an integer or long or some other integer type, but such an algorithm runs this risk of reaching integer overflow when presented with an arbitrarily long input array.

Looking at those cases, I think we can build an explicit, O(n), algorithm that iterates from the least significant digit to the most significant digit changing any 9’s to 0’s until we reach an element less than 9, which we increment, or we have iterated over the entire array. One last step is to check for that third case, all 9’s, by checking if the most siginificant digit has been zeroed and, if so, change the most sigificant digit to 1 and add a 0 to the result. Take a look at the code to see how neatly that all translates:

vector<int> plusOne(vector<int>& digits) {
   for(int i=digits.size()-1;i>=0;i--) {
	  if(digits[i]==9) {
		 digits[i] = 0;
	  }
	  else {
		 digits[i]++;
		 return digits;
	  }
   }
   digits[0] = 1;
   digits.push_back(0);
   return digits;
}