--- layout: page title: Plus One last_solved: 2020-06-05 category: array, math leetcode_url: https://leetcode.com/problems/plus-one/ status: Solved --- Problem ------- ``` Given a non-empty array of digits representing a non-negative integer, plus one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself. Example 1: Input: [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123. Example 2: Input: [4,3,2,1] Output: [4,3,2,2] Explanation: The array represents the integer 4321. ``` Solution ---------- {% highlight python %} def plusOne(self, digits: List[int]) -> List[int]: ptr = len(digits)-1 carry = 1 # just set carry=1 to do get into the loop while carry==1: # edge case when carry=1 and ptr goes left off the edge (ie: '9') if ptr<0: digits.insert(0, 1) return digits # normal case: just add one to last digit if digits[ptr]>=0 and digits[ptr]<9: digits[ptr] = digits[ptr]+1 carry=0 return digits # edge case, set carry and move left elif digits[ptr]==9: digits[ptr] = 0 carry = 1 ptr-=1 return digits {% endhighlight %} ________________ Another solution by converting to int, adding 1 and converting back to list. For really big numbers, use ```//``` instead of ```/``` and ```pow(x,y)``` or ```x**y``` instead of ```math.pow(x,y)```. It makes a difference when N is large. {% highlight python %} import math # digits = [6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,5,4,3] digits = [7,2,8,5,0,9,1,2,9,5,3,6,6,7,3,2,8,4,3,7,9,5,7,7,4,7,4,9,4,7,0,1,1,1,7,4,0,0,6] def plusOne(digits): num = 0 exp = 0 for i in reversed(range(len(digits))): print(num, i, exp, digits[i], pow(10, exp), math.floor( digits[i] * pow(10, exp))) num += math.floor( digits[i] * pow(10, exp)) exp+=1 plusOne = int(num+1) res = [] while plusOne>0: pop = plusOne%10 res = [pop] + res plusOne = plusOne//10 return res print(plusOne(digits)) {% endhighlight %} __________________ - [stackoverflow about //](https://stackoverflow.com/questions/27946595/how-to-manage-division-of-huge-numbers-in-python) - [stackoverflow about pow](https://stackoverflow.com/questions/10282674/difference-between-the-built-in-pow-and-math-pow-for-floats-in-python) ``` Using ```math.pow(x,y)``` 0 38 0 6 1.0 6 6 37 1 0 10.0 0 6 36 2 0 100.0 0 6 35 3 4 1000.0 4000 4006 34 4 7 10000.0 70000 74006 33 5 1 100000.0 100000 174006 32 6 1 1000000.0 1000000 1174006 31 7 1 10000000.0 10000000 11174006 30 8 0 100000000.0 0 11174006 29 9 7 1000000000.0 7000000000 7011174006 28 10 4 10000000000.0 40000000000 47011174006 27 11 9 100000000000.0 900000000000 947011174006 26 12 4 1000000000000.0 4000000000000 4947011174006 25 13 7 10000000000000.0 70000000000000 74947011174006 24 14 4 100000000000000.0 400000000000000 474947011174006 23 15 7 1000000000000000.0 7000000000000000 7474947011174006 22 16 7 1e+16 70000000000000000 77474947011174006 21 17 5 1e+17 500000000000000000 577474947011174006 20 18 9 1e+18 9000000000000000000 9577474947011174006 19 19 7 1e+19 70000000000000000000 79577474947011174006 18 20 3 1e+20 300000000000000000000 379577474947011174006 17 21 4 1e+21 4000000000000000000000 4379577474947011174006 16 22 8 1e+22 80000000000000000000000 84379577474947011174006 15 23 2 1e+23 199999999999999983222784 284379577474946994396790 14 24 3 1e+24 2999999999999999949668352 3284379577474946944065142 13 25 7 1e+25 70000000000000008489271296 73284379577474955433336438 12 26 6 1e+26 600000000000000062948114432 673284379577475018381450870 11 27 6 1e+27 6000000000000000629481144320 6673284379577475647862595190 10 28 3 1e+28 30000000000000000948382466048 36673284379577476596245061238 9 29 5 1e+29 499999999999999939573568241664 536673284379577416169813302902 8 30 9 1e+30 8999999999999999897486646837248 9536673284379577313656460140150 7 31 2 1e+31 19999999999999999271792589930496 29536673284379576585449050070646 6 32 1 1e+32 100000000000000005366162204393472 129536673284379581951611254464118 5 33 9 1e+33 9000000000000000086637831186808832 9129536673284379668589442441272950 4 34 0 1e+34 0 9129536673284379668589442441272950 3 35 5 1e+35 499999999999999947423342392170774528 509129536673284327091931834612047478 2 36 8 1e+36 8000000000000000339365098992143695872 8509129536673284666457030826755743350 1 37 2 1e+37 19999999999999999077525316404242284544 28509129536673283743982347230998027894 0 38 7 1e+38 700000000000000003131134695670819061760 [7, 2, 8, 5, 0, 9, 1, 2, 9, 5, 3, 6, 6, 7, 3, 2, 8, 6, 8, 7, 5, 1, 1, 7, 0, 4, 2, 9, 0, 1, 8, 1, 7, 0, 8, 9, 6, 5, 5] ___________________ Using ```pow(x,y)``` 0 38 0 6 1 6 6 37 1 0 10 0 6 36 2 0 100 0 6 35 3 4 1000 4000 4006 34 4 7 10000 70000 74006 33 5 1 100000 100000 174006 32 6 1 1000000 1000000 1174006 31 7 1 10000000 10000000 11174006 30 8 0 100000000 0 11174006 29 9 7 1000000000 7000000000 7011174006 28 10 4 10000000000 40000000000 47011174006 27 11 9 100000000000 900000000000 947011174006 26 12 4 1000000000000 4000000000000 4947011174006 25 13 7 10000000000000 70000000000000 74947011174006 24 14 4 100000000000000 400000000000000 474947011174006 23 15 7 1000000000000000 7000000000000000 7474947011174006 22 16 7 10000000000000000 70000000000000000 77474947011174006 21 17 5 100000000000000000 500000000000000000 577474947011174006 20 18 9 1000000000000000000 9000000000000000000 9577474947011174006 19 19 7 10000000000000000000 70000000000000000000 79577474947011174006 18 20 3 100000000000000000000 300000000000000000000 379577474947011174006 17 21 4 1000000000000000000000 4000000000000000000000 4379577474947011174006 16 22 8 10000000000000000000000 80000000000000000000000 84379577474947011174006 15 23 2 100000000000000000000000 200000000000000000000000 284379577474947011174006 14 24 3 1000000000000000000000000 3000000000000000000000000 3284379577474947011174006 13 25 7 10000000000000000000000000 70000000000000000000000000 73284379577474947011174006 12 26 6 100000000000000000000000000 600000000000000000000000000 673284379577474947011174006 11 27 6 1000000000000000000000000000 6000000000000000000000000000 6673284379577474947011174006 10 28 3 10000000000000000000000000000 30000000000000000000000000000 36673284379577474947011174006 9 29 5 100000000000000000000000000000 500000000000000000000000000000 536673284379577474947011174006 8 30 9 1000000000000000000000000000000 9000000000000000000000000000000 9536673284379577474947011174006 7 31 2 10000000000000000000000000000000 20000000000000000000000000000000 29536673284379577474947011174006 6 32 1 100000000000000000000000000000000 100000000000000000000000000000000 129536673284379577474947011174006 5 33 9 1000000000000000000000000000000000 9000000000000000000000000000000000 9129536673284379577474947011174006 4 34 0 10000000000000000000000000000000000 0 9129536673284379577474947011174006 3 35 5 100000000000000000000000000000000000 500000000000000000000000000000000000 509129536673284379577474947011174006 2 36 8 1000000000000000000000000000000000000 8000000000000000000000000000000000000 8509129536673284379577474947011174006 1 37 2 10000000000000000000000000000000000000 20000000000000000000000000000000000000 28509129536673284379577474947011174006 0 38 7 100000000000000000000000000000000000000 700000000000000000000000000000000000000 [7, 2, 8, 5, 0, 9, 1, 2, 9, 5, 3, 6, 6, 7, 3, 2, 8, 4, 3, 7, 9, 5, 7, 7, 4, 7, 4, 9, 4, 7, 0, 1, 1, 1, 7, 4, 0, 0, 7] ``` ____________ Another way is to cast it: {% highlight python %} print( [str(d) for d in digits] ) # cast every int to string in list ["1", "2", "3"] str1 = "".join([str(d) for d in digits]) # string join to get "123" print( str1 ) plusOne = int(str1)+1 # cast it to an int and add 1 print( plusOne ) # back to digit array return [int(d) for d in str(plusOne)] # cast every char in string to an int and return as list {% endhighlight %} ![image1]()