[Math] Plus One[Facebook]

1. Example
123 (MSB-> LSB) + 1 = 124
999+ 1 = 1000

2. Implementation
MSB->LSB so loop from the end of array and replace with calculated result in place
so time should be O(n) and space should be constant O(1). However, for the case 999+1=1000,
we need an extra digit, that's why a new array comes into the picture and take up O(n) space
Follow Up: LSB->MSB loop from the start of array and replace with calculated result in place
Follow Up: input is linked list (LSB->MSB) => Add Binary
Follow Up: input is linked list (MSB->LSB)

// Time :O(n) go over the array, Space:O(n) a new array for return
public class Solution extends Exception
{
    public int[] plusOne(int[] digits) 
    {
         // valid the input
         if (digits == null || digits.length ==0)
         {
              return digits;
         }



         int carry = 1; // plus one
         for (int i = digits.length-1; i>= 0 ; i--)
         {
              int sum = digits[i] + carry ;
              carry = sum / 10;
              digits[i] = sum % 10;
         }
         


         // check overflow
         if (carry == 1 )
         {
              int[] res = new int[digits.length+1];
              res[0] = carry;
              for (int i = 0 ; i < digits.length; i++)
              {
                    res[i+1] = digits[i];
              }
              return res;
         } 
         else if (carry == 0)
         {
              return digits;
         } 
         else 
         {
              throw new Exception("Unexpected result");
         }

    }
}

3. Similar Ones
[String](M) Multiply Strings
(E) add binary

http://alvinalexander.com/java/java-custom-exception-create-throw-exception