233 lines
8.1 KiB
Markdown
233 lines
8.1 KiB
Markdown
---
|
|
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]() |