Skip to main content

Snippets

Convex function​

while left < right:
    mid = left + (right - left) // 2
    y1 = f(mid); y2 = f(mid + 1)
    res = min(y1, y1)
    if y1 < y2: right = mid
    else: left = mid + 1

Divisors of numbers between 1 to n​

def getDivisors(n):
    divisors = [[] for _ in range(n+1)]
    for i in range(1, n+1):
        j = i
        while j <= n:
            divisors[j].append(i)
            j += i
    return divisors

Fenwick Tree​

class FenwickTree:
  def __init__(self, n):
    self.size = n
    self.vals = [0] * (n + 1)

  def update(self, i, val):
    i += 1
    while i <= self.size:
      self.vals[i] += val
      i += i & -i

  def query(self, i):
    i += 1; res = 0
    while i:
      res += self.vals[i]
      i -= i & -i
    return res

GCD And LCM​

def gcd(num1, num2):
  a, b = num1, num2
  while b:
    a, b = b, a % b
  return a

gcd = gl(num1, num2)
lcm = (num1 * num2) // a

Median​

n = len(nums)
median = (nums[n >> 1] + nums[~(n >> 1)]) / 2

Palindromes​

n = len(s)
dp = [[True] * n for _ in range(n)]
for i in range(n-1, -1, -1):
    for j in range(i+1, n):
        dp[i][j] = s[i] == s[j] and dp[i+1][j-1]

Union Find​

def find(x):
    if root[x] != x:
      root[x] = find(root[x])
    return root[x]

root = list(range(n))
for u, v in edges:
  root[find(u)] = find(v)