plusOne.md

Requirements

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

• input: array of positive integers, representing an integer
• output: array of positive integers, representing the input integer plus one
• constraints:
• edge case: [9]

Strategy

• Go through the array backwards
• add 1 to the current index
• if the index value exceeds 9, set it to zero and continue
• otherwise return the array

Justification of strategy

Since we're adding 1 to a whole integer, the first thing to change will be the right most digit, therefore it makes sense to start at the end of the array and go backwards. Furthermore, we only need to continue moving through the array, if the value of the current index becomes 10

Define test cases

[ 1, 0, 0] => [1, 0, 1]

[9] => [1, 0]

[0] => [1]

[9, 9, 9, 9] => [1, 0, 0, 0, 0]

[1, 2, 9, 9] => [1, 3, 0, 0]

Implementation skeleton

• loop through the input array backwards
  • set the current index value to equal itself plus 1
  • if the current index value is greater than 9
    • set the current index value to 0
    • if the current index is 0
      • unshift 1 to the array
• return the input array

Actual implementation

https://repl.it/@pmillssf/PlusOne

Execute test cases

run https://repl.it/@pmillssf/PlusOne

Big-O Analysis

Time: O(n)

Space: O(1)

Optimization (if applicable)