Problem

• https://leetcode.com/problems/plus-one
• https://leetcode.cn/problems/plus-one （中文）

Data Structure

• Array

Intuition

• Travel through from the last item.

Routine

• If number is less than 9, plus 1 then return the digits
  • The last digit (1st step):
    • Initial plus 1
  • Other digits:
    • Carry from the digit on the right (index + 1)
  • Early exist: No need to carry to the next digit, can early exist.
• If number is >= 9 means needed to carry
  • Set to 0
  • Continue

End of routine

When go through every digits without return, means we have a carry from the highest digit, so that we have to insert a 1 to the digits[0]

Code

class Solution {
    func plusOne(_ digits: [Int]) -> [Int] {
        var index = digits.count - 1
        var digits = digits

        while index >= 0 {
            if digits[index] < 9 {
                digits[index] += 1
                return digits
            }
            digits[index] = 0
            index -= 1
        }

        digits.insert(1, at: 0)
        return digits
    }
}

Complexity

• Time Complexity: O(n)
  • Linear travel of the array.
• Space Complexity: O(n)
  • * Need to copy an array for mutable purpose. If not consider this can be O(1)

End of post

That's it!

Please leave comment if you have any comments, thanks for your reading!