[Python] Find maximum number of 9 in the end, explained
How we can add 1 to given number? We need to find the biggest number of 9 in the end of our number, for example for number 5123521999235123999, there will be th
How we can add `1` to given number? We need to find the biggest number of `9` in the end of our number, for example for number `5123521999235123999`, there will be three `9` in the end. `512352199923512`**3999**` + 1 = 512352199923512`**4000**: so we need to increase previous symbol by one and change all `9` after to `0`. Now, the steps of algorithm are to following:\n\n1. Let us add one `0` before our data to handle cases like `9`, `99`, `999`, ... \n2. Find maximum number of `9`, starting from the end and moving to the left.\n3. Change all found `9` in the end to `0` and previous digit increasy by `1`.\n4. Handle border cases: if we have leading zero, remove it.\n\n**Complexity** time complexity is `O(n)`, where `n` is length of list. Additional space complexity is `O(1)`, because we edit input data directly.\n\n```\nclass Solution:\n    def plusOne(self, digits):\n        digits = [0] + digits\n        \n        end = len(digits) - 1\n        while digits[end] == 9:\n            end -= 1\n    \n        digits[end] += 1\n        digits[end+1:] = [0] * (len(digits)-1-end)\n                   \n        return digits if digits[0] != 0 else digits[1:]      \n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
[]