Friedrich Ewald My Personal Website

Leetcode: Plus one

A decimal number is given as a list of integers. The number should be incremented by 1. The idea here is to iterate backwards through the list and start with the smallest digit. This way, this challenge can be solved in O(n). If after adding 1, the mod(10) is 0 it means we had an overflow and need to add one. If we didn’t we’re done and can break the loop. As a final check we need to make sure that there is no overflow in the end which would cause us to prepend the list.

from typing import List

class Solution:
  def plusOne(self, digits: List[int]) -> List[int]:
    for pos in range(len(digits)-1, -1, -1):
      remainder = 0
      digits[pos] = (digits[pos] + 1) % 10
      if digits[pos] == 0:
        remainder = 1
        remainder = 0
    if remainder == 1:
      digits = [1] + digits
    return digits

if __name__ == '__main__':
  s = Solution().plusOne
  print(s([1,2,3]), [1,2,4])
  print(s([4,3,2,1]), [4,3,2,2])
  print(s([9]), [1,0])
Runtime: 67 ms, faster than 12.59% of Python3 online submissions for Plus One. Memory Usage: 13.9 MB, less than 59.15% of Python3 online submissions for Plus One.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.