# Learning Python3 C1

#### Integer Math

Posted by Riino on June 26, 2019 Python Algorithm

[TOC]

## Before Math

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.

## Integer: Basic Attributes

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


## Integer: Get Each Number

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-empty linked lists representing two non-negative integers. The digits are stored in reverse order and 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


## Integer: Division From Basic

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)