66.Plus One
Tags: [list], [array]
Com: {g}
Link: https://leetcode.com/problems/plus-one/\#/description
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.
Solution:
class Solution(object):
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
if not digits:
raise ValueError('the input is invalid')
carry = 1
for i in xrange(len(digits) - 1, -1, -1):
tmp = digits[i] + carry
digits[i] = tmp % 10
carry = tmp / 10
if carry > 0:
digits.insert(0, carry)
return digits
Revelation:
- Here we assume the interviewer tell us that we can modify he given input.
- In Python, list.insert(position, val).
Note:
- Time complexity = O(n), n is the number of elements in the given array.
- Space complexity = O(1).