- Step1 : divide number by 2 and add 2 as factor till possible
- Step2 : Start k from 3 with step of 2 till sqrt(number), divide number by k and add k as factor till possible
- Step3 : Check if number remaining is greater than 1, add that number as another factor.
def getPrimeFactors(n):
factors = []
while n%2==0:
factors.append(2)
n = n//2
k=3
while k*k <= n:
if n%k==0:
n= n//k
factors.append(k)
else:
k+=2
if n>1:
factors.append(n)
return factors
>> getPrimeFactors(36)
>> [2, 2, 3, 3]
>> getPrimeFactors(999999901)
>> [61, 463, 35407]
>> getPrimeFactors(4410)
>> [ 2, 3, 3, 5, 7, 7 ]
- Now, 4410 = 2^a * 3^b * 5^c * 7^d
- a could be (0,1), b could be (0,1,2) and so on.
- Total Factors will be 232*3 = 36
from collections import defaultdict
def totalFactors(n):
count = defaultdict(int)
for a in getPrimeFactors(n):
count[a]+=1
total = 1
for cnt in count.values():
total*=(cnt+1)
return total
>> totalFactors(100)
>> 9
def factors(n):
fact = []
for i in range(1, int(n**0.5)+1):
if n%i == 0:
if n//i == i:
fact.append(i)
else:
fact.append(i)
fact.append(n//i)
return fact
>> factors(100)
>> [1, 2, 4, 5, 10, 20, 25, 50, 100]
- Euclidean Method
- GCD(a,b,c) = GCD(a,gcd(b,c))
- (100,24,6) -> (24,4,6) -> (4,0,6) -> (4,6) -> (6,4) -> (4,2) -> (2,0) -> 2
from functools import reduce
def GCD(*args):
gcd2 = lambda a,b: a if b==0 else gcd2(b,a%b)
return reduce( gcd2 , args )
>> a = [9,6,18]
>> GCM(*a)
3
- Euclidean Method
- LCM(a,b) = a*b/GCD(a,b)
- LCM(a,b,c) = LCM(a,LCM(a,b))
from functools import reduce
def LCM(*args):
lcm2 = lambda a,b : int(a*b/GCD(a,b))
return reduce( lcm2 , args )
>> a = [3,9,6]
>> LCM(*a)
18
- It is a way to represent GCD in terms of coefficients a and b i.e. coefficient x and y. ax + by = gcd(a,b)
- https://www.youtube.com/watch?v=6KmhCKxFWOs and https://cp-algorithms.com/algebra/extended-euclid-algorithm.html
def egcd(a, b):
x,y, u,v = 0,1, 1,0
while a != 0:
q, r = b//a, b%a
m, n = x-u*q, y-v*q
b,a, x,y, u,v = a,r, u,v, m,n
gcd = b
return gcd, x, y
>> egcd(56,15)
>> (1, -4, 15)
def egcd(a, b):
x,y, u,v = 0,1, 1,0
while a != 0:
q, r = b//a, b%a
m, n = x-u*q, y-v*q
b,a, x,y, u,v = a,r, u,v, m,n
gcd = b
return gcd, x, y
def find_any_solution(a,b,c): #ax+by = c
g,x0,y0 = egcd( abs(a), abs(b) )
if c%g != 0: #no integer solution
return False
x0 *= c//g
y0 *= c//g
if a<0: x0 = -1*x0
if b<0: y0 = -1*y0
return x0,y0,g
def find_all_solutions(a,b,c):
soln = find_any_solution(a,b,c)
if not soln:
return False
x0,y0,g = soln
k=0
while True:
yield x0+k*(b/g), y0-k*(a/g)
k+=1
- Sieve of Eratosthenes is an ancient method for finding prime numbers
- starting from lowest element(curr) in sieve remove element if item%curr==0
def primes(end,start=0):
is_prime = [True]*(end+1)
is_prime[0] = is_prime[1] = False
prime_list = []
for i in range(2,end+1):
if is_prime[i]:
prime_list.append(i)
for j in range( i*i, end+1, i):
is_prime[j] = False
return prime_list
- Check for every number b/w (2,sqrt(n)), if number is evenly divisible by any then it is not prime
def isPrime(n):
if n<=2: return True if n==2 else False
if n%2==0: return False
for i in range(3,int(n**0.5)+1,2):
if n%i==0: return False
return True
>> isPrime(21)
False
>> isPrime(37)
True
- Simple Binary search to avoid coding this during time of competitive coding.
def binSearch(arr,value, key= lambda x : x):
l,h = 0,len(arr)-1
while l<=h:
x = (h+l)//2
k = key(arr[x])
if value < k:
h = x-1
elif value > k:
l = x+1
else:
return x
return -1
- We can also use bisect_left or bisect_right which has similar functionality as upper_bound and lower_bound in c++.
from bisect import bisect_left, bisect_right
>> arr = [1,2,5,5,9,10]
>> bisect_left( arr, 5 )
2
>> bisect_right( arr, 5 )
4
def bisect_left(array, value):
l,h = 0, len(array)-1
if h==-1: return 0
first_pos = float('inf')
while l<=h:
x = (l+h)//2
if array[x] < value: l = first_pos = x+1
else:
if x < first_pos: first_pos = x
h = x-1
return first_pos
def bisect_right(array,value):
l,h = 0, len(array)-1
last_pos = 0
while l<=h:
x = (l+h)//2
if array[x] > value:
if x < last_pos: last_pos = x
h = x-1
else:
last_pos = l = x+1
return last_pos
_______________ (x4,y4)
| |
______|____B(x2,y2) |
| | | |
|______|____| |
(x1,y1) | A |
|_______________|
(x3,y3)
- A = max(x1,x3), max(y1,y3)
- B = min(x2,x4), min(y2,y4)
- if B.x < A.x or B.y < A.y then no intersection
def intersection(x1,y1,x2,y2,x3,y3,x4,y4):
#x1, y1, x2, y2 -> bottom left and top right of first rect, similar for second
a,b,c,d = max(x1,x3), max(y1,y3), min(x2,x4), min(y2,y4)
if b > d or a > c: return -1
else: return a,b,c,d
- We Will maintain 2 data structures a) for each node w, the number of incoming edges w has from active nodes (nodes that not have been deleted). b) the set S of all active node in G that has no incoming edges from other active nodes
- At start all nodes are active, do a linear pass over all edges and initialize above two data structures.
- For each iteration select a node v from S and delete it and print it.
- After deleting v, subtract 1 from number of incoming edges of node u that has an edge from v.
- Go to step 2
#n is number of nodes
graph = defaultdict(list)
incoming_edges = [0]*n
for b,a in edges:
graph[b].append(a)
incoming_edges[a]+=1
active_nodes = [ i for i in range(n) if incoming_edges[i]==0 ]
order = []
while len(active_nodes) != 0:
curr = active_nodes.pop()
order.append(curr)
for child in graph[curr]:
incoming_edges[child] -= 1
if incoming_edges[child] == 0:
active_nodes.append(child)
if len(order) != n:
return [] #no topological order, cycle is present
else:
return order
- For window of size "window", find out minimum of it.
- Use queue, if first element in queue is "window" length away then pop first element
- if last element in queue is greater than current element then pop last element
from queue import deque
def getRollingMin(array, window):
n = len(array)
q = deque([])
result = []
for i in range(n):
val = array[i]
while len(q) > 0 and q[0][0] <= i-window: q.popleft()
while len(q) > 0 and q[-1][1] >= val: q.pop()
q.append( (i, val) )
if i >= window-1:
result.append( q[0][1] )
return result
array = [856, 276, 408, 899, 928, 580, 186, 735, 725, 204]
x = 4
getRollingMin(space, x)
- Dynamic Programming
- LCSS[i][j] = 1 + LCSS[i+1][j+1] if S1[i] == S2[j]
- LCSS[i][j] = 0 + max( LCSS[i+1][j], LCSS[i][j+1] ) otherwise
- Hint: Use loop backwards to calculate these values (to avoid overflow error)
def length(i,j):
if grid[i][j]!=-1:
return grid[i][j]
elif s1[i] != s2[j]:
if i+1 >= w or j+1 >= w:
if i+1 < w: grid[i][j] = length(i+1,j)
if j+1 < w: grid[i][j] = length(i,j+1)
grid[i][j] = max(0, grid[i][j])
else:
grid[i][j] = 0+max( length(i+1,j), length(i,j+1) )
else:
if i+1 >= w or j+1 >= w:
grid[i][j] = 1
else:
grid[i][j] = 1 + length(i+1,j+1)
return grid[i][j]
- In some problems you are asked to give answer in terms of modulo of some prime(M) (say, 1e9+7)
- This is done to reduce the size of answer
- For example:
- (a+b)%M = ( a%M + b%M ) % M
- (a-b)%M = ( a%M - b%M ) % M
- (a.b)%M = ( a%M . b%M ) % M
- BUT, (a/b)%M != ( a%M / b%M ) % M, Here we will use multiplicative inverse of b
- (a/b) % M = ( a . b^-1 ) % M = ( a%M . (b^-1)%M ) % M, How to find multiplicative inverse of b
- a.a^-1 % M = 1 ---eq(1)
- **By Fermet's Little Theoram, if M is prime, a^(M-1) % M = 1 **
- Ex, a=2,m=5 we have 2^(4) % 5 = 16%5 = 1
- a.a^(M-2) % M == 1 By Fermet's Theoram
- a^-1 = a^(M-2) ---using eq(1)
- Thus multiplicate inverse of a is a^(M-2)
def moduloMulInv(a,M):
return (a**(M-2))%M
- While taking a^n where n is a large number, it is quite time consuming so we use exponential squaring
- Visit link for more info
- Instead Use pow(a,b,z=mod), it calculates (a**b)%z using exponential squaring
def expSqr(a,n):
if n<0 : return expSqr( 1/a, -1*n )
if n==1: return a
if n==0: return 1
if n%2==0:
return expSqr( a*a, n//2 )
else:
return (a%n) * (expSqr( a*a, (n-1)//2 ))
- Instead of seaching a list everytime to see if item is visited which is O(n), use lookups,
- Create lookup as
lookup = [False]*n, and see if item is visited, this is of TC : O(1)
- Also use this function to keep track of time taken by each function anywhere, it outputs in stderr so will not mess up stdout
def giveruntime(func):
import time,sys
def wrap(*args,**kwargs):
s = time.time()
ans = func(*args,**kwargs)
print( "Time taken", time.time()-s, file=sys.stderr )
return ans
return wrap
@giveruntime
def forLoop(n=1000000):
for i in range(n): pass
@giveruntime
def whileLoop(n=1000000):
i = 0
while i<n: i+=1
>> forLoop(999999999)
Time taken 41.75519561767578
>> whileLoop(999999999)
Time taken 104.35621953010559
- Suitable where we have to sort limited range of items. Not good for large range of item values.
- Initialize an array with size equal to range of total items as all zeros.
- Increase the count at each index with index equal to value of item
def CountingSort(values):
arr = [ 0 for _ in range(max(values)) ]
for a in values: arr[a]+=1
sortedval = []
for i in range(len(arr)):
sortedval += [i]*arr[i]
return sortedval
- Very practical, Inplace, No extra memory. Hower unstable
- On average runs in O(nlogn) time complexitiy.
- Key idea is to select a pivot. This pivot divides the array in 2 halves, one with numbers smaller than pivot and other numbers greater than pivot. After this pivot is at the correct position.
import random
def quickSort( arr, low=0, high=None, pivot="random" ):
"""
pivot :
first, last, middle, random
"""
if high == None: high = len(arr)-1
if high-low >= 1:
pvt = None
if pivot == 'first': pvt = low
elif pivot == 'last': pvt = high
elif pivot == 'middle': pvt = low + (high-low)//2
else: pvt = random.randint( low, high )
partn, comparisions = partition( arr, low, high, pvt )
comparisions += quickSort( arr, low, partn-1, pivot=pivot )
comparisions += quickSort( arr, partn+1, high, pivot=pivot )
return comparisions
else:
return 0
def partition( arr, low, high, pvt ):
arr[pvt], arr[high], pvt = arr[high], arr[pvt], high #swap high with choosen pivot
pivot = arr[pvt] #pivot element
idx = low #pointer to last switched element
ptr = low #pointer to current element to compare
comparisions = 0
#routine with high as pivot
while ptr <= high-1:
comparisions+=1
if arr[ptr] < pivot:
arr[ptr], arr[idx] = arr[idx], arr[ptr]
idx+=1
ptr+=1
arr[idx], arr[pvt] = pivot, arr[idx]
return idx, comparisions
- Application : Algorithm doing repeated minimum operations, heap sort, priority queue (event manager), median maintance,
- Running Time : O(logn) - Insertion, O(logn) - extract min, O(nlogn) - heapify, O(logn) - deletion
- Improvement : Implement decreaseKey in O(logn), maintain a hash table with all key pointing to their position.
class Heap():
def __init__(self, arr=[], key=lambda x: x, value=lambda x: x):
self.arr = arr
self.key = key
self.value = value
self.hashtable = dict()
for i in range(len(self)):
self.hashtable[ self.__getValue(i) ] = i
self.heapify()
def __repr__(self): return f"{self.arr}"
def __len__(self): return len(self.arr)
def __getitem__(self, i): return self.key( self.arr[i] )
def peek(self): return self.arr[0]
def isEmpty(self): return len(self)==0
def __swap_hash_indices(self, i,j):
self.hashtable[ self.__getValue(i) ], self.hashtable[ self.__getValue(j) ] = \
self.hashtable[ self.__getValue(j) ], self.hashtable[ self.__getValue(i) ]
def __getValue(self, i):
return self.value(self.arr[i])
def __iter__(self):
while len(self)>0:
yield self.extractMin()
def getItem(self, val):
return self.arr[self.hashtable[val]]
def checkVal(self, val):
return val in self.hashtable
def heapify(self):
for i in range( (len(self)+1)//2, -1, -1 ):
self.__bubble_down(i)
def insert(self, val):
self.arr.append(val)
self.hashtable[ self.__getValue(len(self)-1) ] = len(self)-1
self.__bubble_up(len(self)-1)
def extractMin(self):
self.arr[0], self.arr[-1] = self.arr[-1], self.arr[0]
self.__swap_hash_indices(0, len(self)-1)
self.hashtable.pop( self.__getValue(len(self)-1) )
ans = self.arr.pop()
self.__bubble_down(0)
return ans
def updateKey(self, val):
key = self.key(val)
idx = self.hashtable[ self.value(val) ]
old_key = self[idx]
self.arr[idx] = val
if key < old_key: self.__bubble_up(idx)
elif key > old_key: self.__bubble_down(idx)
else: pass
def __bubble_up(self, idx):
parent = (idx-1)//2
while parent >=0 and self[idx] < self[parent]:
self.__swap_hash_indices(idx, parent)
self.arr[idx], self.arr[parent] = self.arr[parent], self.arr[idx]
idx, parent = parent, (parent-1)//2
def __bubble_down(self, idx):
high = len(self)
while True:
l, r = (2*idx)+1, (2*idx)+2
if r<high:
if self[l] > self[r]:
if self[r] >= self[idx]: break
self.__swap_hash_indices( idx, r )
self.arr[idx], self.arr[r] = self.arr[r], self.arr[idx]
idx = r
else:
if self[l] >= self[idx]: break
self.__swap_hash_indices( idx, l )
self.arr[idx], self.arr[l] = self.arr[l], self.arr[idx]
idx = l
elif l<high:
if self[l] >= self[idx]: break
self.__swap_hash_indices( idx, l )
self.arr[idx], self.arr[l] = self.arr[l], self.arr[idx]
idx = l
else:
break
-
Description : Maintaines a partition of set of objects. Supports two operation find and union.
1. Find(x) : returns the name of grp to which object belong. O(1) 2. Union(Ci,Cj): fuse groups Ci and Cj in one group. O(logn) -
Application : Clustering, Kruskals algorithm
-
Algorithm : Maintain a link for each vertex in connected component. Designate any one vertex in component as leader vertex. Other vertex in that component point to its leader vertex. When doing find just return the leader. When doing union, change the leader of object in smaller component to leader of larger component.
-
Union by rank and Path Compression:
1. All ranks are initialized as 0 2. During union the leader with smaller rank will point to the leader of larger rank. 3. If rank of both leaders are equal then point any one to other one, and increase rank of leader being pointedby 1.- Path Compression - During find change leader of all intermediate vertex as the root. No need to change ranks, rank lemma still hold true. - HopCraft and Ullma
- Now Union and Find running time is log*n i.e. number of times you need to apply log2 so result is <=1
class UnionFind():
def __init__(self):
self.rank = {}
self.leader = {}
def __repr__(self):
return f""" Ranks : {self.rank}, leaders : {self.leader} """
def find(self,x):
leader = self.leader.get(x, x)
if leader != x:
leader = self.find(leader)
self.leader[x] = leader
return leader
def getRank(self,x):
return self.rank.get( x, 0)
def union(self,x,y):
leader1 = self.find(x)
leader2 = self.find(y)
if leader1 == leader2 : return
if self.getRank(leader1) > self.getRank(leader2):
self.leader[leader2] = leader1
elif self.getRank(leader1) < self.getRank(leader2):
self.leader[leader1] = leader2
else:
self.leader[leader1] = leader2
self.rank[leader2] = 1 + self.getRank(leader2)
- In computer science, a trie, also called digital tree or prefix tree, is a type of search tree, a tree data structure used for locating specific keys from within a set.
from collections import defaultdict
class TrieNode:
def __init__(self):
self.children = defaultdict(TrieNode)
self.end = True
def __repr__(self): return f"{dict(self.children)}"
class Trie:
def __init__(self, words):
self.root = TrieNode()
if len(words) != 0: self.root.end = False
for word in words: self.add(word)
def add(self, word):
node = self.root
for i in range(len(word)):
if word[i] in node.children:
node = node.children[ word[i] ]
else:
node = node.children[ word[i] ]
node.end = False
node.end = True
def search(self, word):
node = self.root
for i in range(len(word)):
if word[i] in node.children:
node = node.children[ word[i] ]
else: return False
return node.end
- Balancing factor of node in AVL tree is (Height of left subtree - Height of Right subtree). Balancing property is maintained by using this balancing factor. For balanced tree, balancing factor of node can be +1, 0, or -1.
- Left Rotate : The arrangement of the nodes on right is transformed into the arrangement on the left node
p p p
| | p |
x x y x | y
/ \ -> / \ \ -> / \ y -> / \
a y a b c a b \ x c
/ \ c / \
b c a b
- Right Rotate : The arrangement of the nodes on the left is transformed into the arrangement on the right node.
p p p
| | p |
y y x | x
/ \ -> / \ / -> x y -> / \
x c b c a / / \ a y
/ \ a b c / \
a b b c
- Lef-Right and Right-Left Rotate
Left-Right Rotate
p p p
| | |
z (2) z (2) y (0)
/ \ / \ / \
(-1) x d -> y d -> x z
/ \ Left / \ Right / \ / \
a y Rotation x c Rotate a b c d
/ \ on x-y / \ on y-z
b c a b
Right-Left Rotate
p p p
| | |
z (-2) z (-2) y (0)
/ \ / \ / \
f x -> f y -> z x
/ \ Right / \ Left / \ / \
y c Rotation a x Rotate f a b c
/ \ on x-y / \ on z-y
a b b c
- Less balanced compared to AVL trees, but involves less rotations during insertions and deletion.
- Generally used when insertion and deletion is less frequent but search is frequent.
- A chain of three nodes is not possible in Red-Black tree.
Interesting points about Red-black trees
- Black height of red-black tree is number of black nodes on a path from root node to leaf node. Leaf nodes are also counted as black nodes. So, a red-black tree of height h has black height >= h/2.