Math / Number Theory Pattern¶

import math
from functools import reduce

class Solution:
    """
    Find GCD of entire array using associativity.

    Key Insight: gcd(a, b, c) = gcd(gcd(a, b), c)
    We can chain GCD across all elements.

    Method 1: Using reduce
    Method 2: Using math.gcd with *args (Python 3.9+)

    Time: O(n * log(max_val)) | Space: O(1)
    """
    def findGCD(self, nums: List[int]) -> int:
        # Method 1: Explicit reduce
        return reduce(math.gcd, nums)

        # Method 2: Python 3.9+ allows math.gcd(*nums)
        # return math.gcd(*nums)

    def findGCD_manual(self, nums: List[int]) -> int:
        """Manual implementation without library."""
        def gcd(a: int, b: int) -> int:
            while b:
                a, b = b, a % b
            return a

        result = nums[0]
        for num in nums[1:]:
            result = gcd(result, num)
            if result == 1:  # Early exit: GCD can't go below 1
                break
        return result

def lcm(a: int, b: int) -> int:
    return a * b // math.gcd(a, b)

class Solution:
    """
    Sieve of Eratosthenes: Find all primes up to n.

    Algorithm:
    1. Create boolean array is_prime[0..n], initially all True
    2. Mark 0 and 1 as not prime
    3. For each prime p starting from 2:
       - Mark all multiples of p (p², p²+p, p²+2p, ...) as composite
       - Start from p² because smaller multiples already marked
    4. Count remaining True values

    Time: O(n log log n) | Space: O(n)
    """
    def countPrimes(self, n: int) -> int:
        if n < 2:
            return 0

        # Initialize: assume all are prime
        is_prime = [True] * n
        is_prime[0] = is_prime[1] = False

        # Sieve: mark composites
        for p in range(2, int(n ** 0.5) + 1):
            if is_prime[p]:
                # Mark multiples starting from p²
                for multiple in range(p * p, n, p):
                    is_prime[multiple] = False

        return sum(is_prime)

class Solution:
    """
    Base-26 conversion with 1-indexed twist.

    Key Insight: Excel columns are 1-indexed (A=1, not A=0).
    Standard base-26 is 0-indexed (A=0, B=1, ...).

    Fix: Subtract 1 before each division to shift to 0-indexed,
    then convert remainder to letter.

    Process:
    1. Subtract 1 (shift from 1-indexed to 0-indexed)
    2. remainder = n % 26 → maps to 'A' + remainder
    3. n = n // 26
    4. Repeat until n = 0
    5. Reverse the result (we built from right to left)

    Time: O(log₂₆ n) | Space: O(log₂₆ n)
    """
    def convertToTitle(self, columnNumber: int) -> str:
        result = []

        while columnNumber > 0:
            columnNumber -= 1  # Shift to 0-indexed
            remainder = columnNumber % 26
            result.append(chr(ord('A') + remainder))
            columnNumber //= 26

        return ''.join(reversed(result))

def titleToNumber(self, columnTitle: str) -> int:
    result = 0
    for char in columnTitle:
        result = result * 26 + (ord(char) - ord('A') + 1)
    return result

import math

# GCD of two numbers
gcd_val = math.gcd(a, b)

# GCD of array (Python 3.9+)
gcd_all = math.gcd(*nums)

# GCD of array (older Python)
from functools import reduce
gcd_all = reduce(math.gcd, nums)

# LCM via GCD
lcm_val = a * b // math.gcd(a, b)

# LCM of array
def lcm_array(nums):
    result = nums[0]
    for num in nums[1:]:
        result = result * num // math.gcd(result, num)
    return result

def sieve_of_eratosthenes(n: int) -> List[int]:
    """Return all primes less than n."""
    if n < 2:
        return []
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(n ** 0.5) + 1):
        if is_prime[p]:
            for m in range(p * p, n, p):
                is_prime[m] = False
    return [i for i in range(n) if is_prime[i]]

def is_prime(n: int) -> bool:
    """Check if n is prime. O(√n)"""
    if n < 2:
        return False
    if n == 2:
        return True
    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

def prime_factors(n: int) -> List[int]:
    """Return list of prime factors (with duplicates)."""
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

def mod_pow(base: int, exp: int, mod: int) -> int:
    """Compute base^exp % mod in O(log exp)."""
    result = 1
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        exp //= 2
        base = (base * base) % mod
    return result

# Or use built-in: pow(base, exp, mod)

def to_base(n: int, base: int) -> str:
    """Convert n to given base (2-36)."""
    if n == 0:
        return "0"
    digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    result = []
    while n:
        result.append(digits[n % base])
        n //= base
    return ''.join(reversed(result))

def from_base(s: str, base: int) -> int:
    """Convert string in given base to integer."""
    return int(s, base)