BeginnerAdvanced Patterns

Math & Bits

GCD/LCM, modular arithmetic, and bit manipulation tricks

Time: O(log n) typical
Space: O(1)
Pattern Overview

Core Idea

Exploit mathematical properties and bit operations for constant-time hacks and logarithmic algorithms.

When to Use

Use for parity/counting bits, fast exponentiation, and modular inverses.

General Recognition Cues
General indicators that this pattern might be applicable
  • Bit counts
  • Power/exponent
  • Modulo constraints
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

GCD/LCM

Euclid's algorithm and lcm(a,b)=a/gcd*b

When to Use This Variant
  • Divisibility
Use Case
Ratios/simplify
Advantages
  • Logarithmic
Implementation
def gcd(a,b):
    while b: a,b=b,a%b
    return a
def lcm(a,b):
    return a//gcd(a,b)*b
2

Modular Arithmetic

Fast pow, inverses (when applicable)

When to Use This Variant
  • mod 1e9+7
Use Case
Large combinatorics
Advantages
  • Efficient
Implementation
def mod_pow(a, e, m):
    res=1; a%=m
    while e:
      if e&1: res=res*a%m
      a=a*a%m; e>>=1
    return res
3

Bit Manipulation

Masks, shifts, popcount

When to Use This Variant
  • XOR, AND, OR
Use Case
Low-level tricks
Advantages
  • O(1) per op
Implementation
def count_bits(n):
    cnt=0
    while n:
        n&=n-1
        cnt+=1
    return cnt
Common Pitfalls
Watch out for these common mistakes
  • Overflow
  • Negative modulo
  • Bit precedence
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(log n) typical

Math/bit ops are constant or log.

Space Complexity
O(1)

Constant.

Ready to test your knowledge?

Test your pattern recognition with interactive questions