CodeMosa

Master LeetCode Patterns

BeginnerAdvanced Patterns

Math & Bits

GCD/LCM, modular arithmetic, and bit manipulation tricks

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

What is Math & Bits?

#
Definition: Use math identities and bitwise operations for efficient computations like GCD, fast power, and bit counting.

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.

How Math & Bits works

#

Euclid GCD/LCM, fast modular exponentiation, and common bit tricks (masking, shifts, popcount).

  • Bit counts
  • Power/exponent
  • Modulo constraints

General Recognition Cues

#
General indicators that this pattern might be applicable
  • Bit counts
  • Power/exponent
  • Modulo constraints

Code Templates

#
Euclid GCD/LCM, fast modular exponentiation, and common bit tricks (masking, shifts, popcount).
# Greedy Template (Interval Scheduling)
def interval_scheduling(intervals):
    intervals.sort(key=lambda x: x[1])
    res=[]; end=-10**18
    for s,e in intervals:
        if s>=end:
            res.append([s,e]); end=e
    return res

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

Related Patterns

#
BacktrackingFenwick Tree (Binary Indexed Tree)GreedyKMP AlgorithmRange QueriesSegment Tree

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