Post published over one year ago

[TOC]

Assuming all the compile should be involved in `int32`

type, which means every returned answer should be limited in [-2^31, 2^31-1]

There’s only two basic calculations : Addition and Subtraction , and three basic bool judgments : ‘More than’ , ‘Less than’ and ‘Equal’, which composed all algorithm next.

I personally regard the symbol and the value as two divided attributes in a single integer. Thus, to use if(int<0) to check whether the integer is negative is quite useful, we can quickly multiply -1 to it , and use another variable to save its symbol. It’s useful when the problem do not care symbol, for example, Problem 7: Reverse Integer.

We can simply isolate the symbol, do reverse operation in whatever way you like , and reduce symbol:

```
class Solution:
def reverse(self, x: int) -> int:
if x<0:#check negativity
x=-x
flag=-1
else:
flag=1
s = str(x)
s=s[::-1]
res = int(s)*flag #convert to string and reverse
if res < -2**31 or res>2**31-1: #check overflow
return 0
else:
return res
```

However, everything above can be represented as 3 lines with totally same thought of solution:

```
s = cmp(x, 0)#check negativity
r = int(`s*x`[::-1])#convert to string and reverse
return s*r * (r < 2**31)#check overflow
#By StefanPochmann
```

Some times we need to get each number of a integer, for example (int)1234, we hope we can get 1, 2,3,4 each time, or 4,3,2,1 each time. Next I use Problem 2 : Add Two Numbers as an example.

**Description**

You are given two

non-emptylinked lists representing two non-negative integers. The digits are stored inreverse orderand each of their nodes contain a single digit. Add the two numbers and return it as a linked list.You may assume the two numbers do not contain any leading zero, except the number 0 itself.

**Example**

`Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.`

First we talk about having the sum 807, **How do we get each number of this sum and put it in each node of final linked list?**

We can use such scheme: 123% 10 = 3, 123-3 % 100 = 20 , 123 -20 -3 %1000 = 100 . And 3 /1 =3 , 20/10 = 2 , 100/100 = 1. This law can be used in every integer.

Next, **How we assemble a integer by getting single digit each time?** The answer is quite easy: 3x1=3, 2x10=20,1x100=100. 3+20+100 = 123.

Thus the solution is clear:

```
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
N=0
N1=0
N2=0
while(l1!=None):#get each digit of l1
N1=N1+l1.val*pow(10,N)
l1=l1.next
N=N+1
N=0
while(l2!=None):#get each digit of l2
N2=N2+l2.val*pow(10,N)
l2=l2.next
N=N+1
Sum=N1+N2 #get plused result
length=len(str(Sum))#check number of digits to create nodes
nodes=[]
i=1
while(i<=length):
node=ListNode(int((Sum % pow(10,i))/pow(10,i-1)))#get each digit number of result
nodes.append(node)
i=i+1
for i in range(0,length-1):
nodes[i].next=nodes[i+1]
return nodes[0]
```

However, we can plus each list’s unit’s digit , ten’s digit together at the same time , and put every result in single variable. Moreover, use same loop to put each digit in result linked list , **and use divmod to get each number**.

```
def addTwoNumbers(self, l1, l2):
carry = 0
res = n = ListNode(0)
while l1 or l2 or carry:#while carry :check number of digits to create nodes
if l1:
carry += l1.val#get each digit of l1 and plus
l1 = l1.next
if l2:
carry += l2.val;#get each digit of l2 and plus
l2 = l2.next
carry, val = divmod(carry, 10)#get each digit number of result
n.next = n = ListNode(val)
return res.next
```

Another approach to get each digit is to use `n%10`

For example:

```
while(n>0):
print(n%10)
n/=10
```

**Describpion**

Given two integers

`dividend`

and`divisor`

, divide two integers without using multiplication, division and mod operator.Return the quotient after dividing

`dividend`

by`divisor`

.The integer division should truncate toward zero.

**Example**

```
Input: dividend = 10, divisor = 3
Output: 3
```

At first we all can think of setting a counter, and make subtraction each time like :

```
counter = 0
WHILE dividend > 0
dividend -= divisor
counter++
return counter
```

However, this would be O(n) , which is too slow. We can try to set the ‘divisor’ as large as possible by multiply 2 until it can’t be larger, and then make the subtraction. This will be O(logn):

```
div = divisor //save the divisor
res=0
WHILE dividend > 0
counter = 1
WHILE div < dividend
div<<=1 //<<= is faster than div = div*2
counter<<=1
dividend -= div
res += counter
return res
```

In Python with overflow control:

```
res=0
if ((dividend<0) is (divisor<0)) == False:
flag=-1
else:
flag=1
if dividend==0:
return 0
if dividend==-2147483648 and divisor==-1:
return 2**31-1
dividend=abs(dividend)
divisor=abs(divisor)
while dividend-divisor>=0:
temp=divisor
counter=1
while dividend>=temp*2:
temp=temp*2
counter=counter*2
dividend=dividend-temp
res+=counter
res=res*flag
if res<-2**31 or res>2**31-1:
return 2**31-1
else:
return res
```

Clear vision by lee215:

```
sig = (a < 0) == (b < 0)
a, b, res = abs(a), abs(b), 0
while a >= b:
x = 0
while a >= b << (x + 1): x += 1
res += 1 << x
a -= b << x
return min(res if sig else -res, 2147483647)
```