Math Algorithms

1. Check if a number is perfect square
2. Euclidean Algorithm for GCD
3. Computing Power ($x^n$)
4. Prime Decomposition
5. Power Sets
6. Combinations and Permutations
7. Angular Sweep Algorithm

Check if a number is perfect square

We add 0.5 to avoid the floating point values for very large numbers [Ref]

def check_square (num ):
root = sqrt(num)
int(root + 0.5) ∗∗ 2 == num

Euclidean Algorithm for GCD

If we keep subtracting the small number from the large number, we end up with GCD

def gcd(a,b):	# 	if a > b: a, b = b, a
	if a==0: return b
	return gcd(b%a, a)

Computing Power ($x^n$)

For the below codes, consider $n > 0$. [Leetcode #50]

Recursive Algorithm: Space Complexity: O(logN)

def pow(x,n):
    if n==0: return 1
    if n %2==0: return pow(x,n//2)∗ pow(x,n//2)
    else: return x∗pow(x ,(n−1)//2)∗pow(x ,(n−1)//2)

Iterative Algorithm: Consider n in its binary form, i.e., $b_1 b_2 \cdots, b_{length_limit}$. Now, $x^n = x^{\sum_i b_i 2^i}$. Keep a variable current_product of $x^{2^i}$ and add it to the answer when $b_i$ is 1. Space complexity is O(1).

def pow(x,n):
    current_product , ans= x, 1
    while n >0:
        if n %2==1: ans = ans∗current_product
        current_product = current_product∗current_product
        n = n//2

Prime Decomposition

Decompose any given number into a series of prime factors

def primeDecompose (num ):
    prime_factors , factor = [], 2
    while num >= factor∗factor :
        if num%factor==0:
        	num=num//factor
	        prime_factors.append(factor)
        else: factor +=1
    prime_factors.append (num)
    return prime_factors

Power Sets

Given a set of unique integer nums, return all possible subsets. [Leetcode #78]

Algorithm 1: Cascading Based Approach TC/SC: $O(N.2^N)$

def make_power_set (nums ):
    power_set = [[]]
    for num in nums:
    	new_elems = []
    	for item in power_set :
    		new_elems.append(item + [num])
	power_set = power_set + new_elems
    return power_set

Algorithm 2: Use backtracking/DFS based approach, TC: $O(N.2^N)$ SC: $O(N)$

def make_power_set(nums):
	n = len(nums)
	power_set = []
	def dfs(k, first =0, curr =[]):
		if len(curr)==k:
			power_set.append (curr [:])
			return
		for i in range(first , n):
			curr.append(nums[i]) # add nums[ i ] into the current combination
			dfs(k, i+1, curr) # use next integers to complete the combination
			curr.pop() # backtrack
			return
	for k in range(n+1):
		dfs(k)
	return power_set

Algorithm 3: Bit-masking based, generates lexicographic subsets TC/SC: $O(N.2^N)$

def make_power_set(nums):
	n = len(nums)
	power_set = []
	for i in range (2∗∗n, 2∗∗(n+1)):
		mask = bin(i)[3:]
		curr = []
		for idx , char in enumerate(mask):
			if char=="1": curr.append(nums[idx])
		power_set.append(curr)
	return power_set

Combinations and Permutations

Combinations: Make k-length combinations from n elements. The solution approach is similar to DFS/backtracking with power sets, with fixing the length to k. TC: $O(k.C^N_k)$, SC: $O(C^N_k)$. [Leetcode #77]

def make_combinations(n, k):
    self.out = []
    def dfs(first=0, curr=[]):
        if len(curr)==k:
            self.out.append(curr[:])
        for i in range(first, n):
            curr.append(i)
            dfs(i+1, curr)
            curr.pop()
    dfs()
    return self.out

Permutations: The solution approach is similar to DFS/backtracking with power sets with fixed length n, however, this time we only swap insetad of skipping over the numbers. TC: $O(N.N!)$, SC: $O(N!))$ [Leetcode #46]

def make_permutations(nums):
    n = len(nums)
    self.out = []
    def dfs(first=0):
        if first==n:
            self.out.append(nums[:])
        for i in range(first, n):
            nums[first], nums[i] = nums[i], nums[first]
            dfs(first+1)
            nums[first], nums[i] = nums[i], nums[first]
    dfs()
    return self.out

Angular Sweep Algorithm

Given n points on 2-D plane, find the maximum number of points that can be enclosed by a fixed-radius circle of radius R [Leetcode #1453]

Naive Algorithm: Time Complexity is $O(N^3)$

1. Pick any two points, and make a circle with these two points on the circumference. There will be two circles like that.
2. Find how many points lie inside this circle and return the maximum value

Angular Sweep Algorithm: Time Complexity is $O(N^2 log(N))$

1. For every point, a circle can be defined and rotated such that the given point lies on the circumference.
2. For rest of the points, find the angles when they enter or exit the circle.

[Detailed Mathemtical Analysis and Code]