Popular algorithms

binary_exponentiation.py

"""
Binary Exponentiation computes x^n in O(logn) time.
"""

def pow(x, n):
    result = 1
    power = x
    while n > 0:
        bit = n % 2
        if bit == 1:
            result *= power
        power *= power
        n //= 2
    return result

if __name__ == "__main__":
    print(pow(3, 4))  # 81
    print(pow(3, 13))  # 1,594,323

binary_search.py

from bisect import bisect_left, insort_left

def binary_search(arr, target): 
    # behaves exactly like bisect_left
    # it returns leftmost index where target can be inserted 
    start, end = 0, len(arr)
    while start < end:
        mid = (start + end) // 2
        if target > arr[mid]:
            start = mid + 1
        else:
            end = mid
    return start


if __name__ == '__main__':
    arr = [2, 4, 6, 7, 7, 8]

    for elem in [4, 5]:
        i = binary_search(arr, elem)
        found = arr[i] == elem if i < len(arr) else False
        print(f"elem: {elem}, found: {found}, leftmost index: {i}")
    # 4, True, 1
    # 5, False, 2

    print(bisect_left(arr, 5))  # 2

    arr2 = arr.copy()
    insort_left(arr2, 5)
    print(arr2)  # [2, 4, 5, 6, 7, 7, 8]

euclid-gcd.py

def gcd(a, b):
    while b != 0:
        temp = b
        b = a % b
        a = temp

    return a


if __name__ == '__main__':
    print('Greatest common divisor:', gcd(16, 4))  # greatest no. that can divide both 16 and 4
    print('Lowest common multiple:', (16 * 4) / gcd(16, 4))

is-perfect-square.py

"""
1  = 1
4  = 1 + 3
9  = 1 + 3 + 5
16 = 1 + 3 + 5 + 7
25 = 1 + 3 + 5 + 7 + 9
36 = 1 + 3 + 5 + 7 + 9 + 11
...

1 + 3 + ... + (2*n - 1) = n*n (via AP sum)
"""

def is_perfect_square(num):
    i = 1
    while num > 0:
        num -= i
        i += 2
    return num == 0


if __name__ == '__main__':
    print(is_perfect_square(225))

moore_voting_algorithm.py

"""
https://leetcode.com/problems/majority-element/
"""

def majority_element(nums):
    # find majority element i.e. element with more than n/2 occurrences
    candidate, count = None, 0
    for num in nums:
        if count == 0:
            candidate = num

        if candidate == num:
            count += 1
        else:
            count -= 1
    return candidate

if __name__ == "__main__":
    nums = [3,2,2,3,3,1,3,3,1,3,3,1]  # nums has 12 elements. 3 occurs 7 times
    print(majority_element(nums))  # 3

sieve-of-eratosthenes.py

from math import sqrt


def primes(max):
    nums = list(range(2, max + 1))
    prime, index = 2, 0  # index of prime in nums
    while prime <= sqrt(max):
        # reduce
        nums = nums[:index+1] + [n for n in nums[index+1:] if n % prime != 0]
        # get next prime
        index += 1
        prime = nums[index]

    return nums


if __name__ == '__main__':
    print(primes(47))  # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]