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
No comments:
Post a Comment