Leetcode: Plus One

Plus one to a big integer

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## Blog link: https://code.dennyzhang.com/plus-one
## Basic Ideas: If the highest digit is 1, the value is negative
## Complexity: Time O(n), Space O(n)
class Solution(object):
    def plusOne(self, digits):
        :type digits: List[int]
        :rtype: List[int]
        res = []
        has_carry = False
        if digits[-1] == 9:
            res.insert(0, 0)
            has_carry = True
            res.insert(0, digits[-1]+1)

        for i in range(len(digits)-2, -1, -1):
            if has_carry is False:
                res.insert(0, digits[i])
                if digits[i] == 9:
                    res.insert(0, 0)
                    has_carry = True
                    res.insert(0, digits[i]+1)
                    has_carry = False

        if has_carry is True:
            res.insert(0, 1)
        return res

Share It, If You Like It.

Leave a Reply

Your email address will not be published.