TRT
Sign in

Core · Module 12 · Lesson 3 of 4

Combinatorics, Modular nCr, and the Pigeonhole Principle

Count permutations, combinations, and Catalan structures using precomputed factorials and inverse factorials in O(1) per query, and prove existence guarantees with the Pigeonhole Principle.

Pro — members onlyAbout 18 minutes

By the end you can

  • Precompute factorials and inverse factorials modulo p in O(N) time to answer nCr mod p queries in O(1)
  • Recognize Catalan number recurrences (valid parentheses, BST shapes, polygon triangulations)
  • Use the Pigeonhole Principle and Inclusion-Exclusion to turn search problems into O(N) prefix-remainder checks

Builds on Euclidean GCD, Modular Arithmetic, and Binary Exponentiation, Prime Sieves (Eratosthenes & Linear Sieve) and Prime Factorization.

01 · A question first

Given an array of N integers, why is there ALWAYS a non-empty contiguous subarray whose sum is divisible by N? The Pigeonhole Principle proves it in two sentences—and turns an O(N^2) search into an O(N) prefix-sum lookup.

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • Intuitive Explanation & Real-World Analogy
  • Core Concepts & Visual Walkthrough
  • Pseudocode
  • Multi-Language Implementations (C++, Java, Python)
  • Time & Auxiliary Space Complexity Derivation
  • Edge Cases & Common Beginner Mistakes
  • Alternative Approaches (Brute Force vs. Optimal)
  • Pattern Recognition Guide & Three-Stage Practice Plan
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeUnique paths IICount right-and-down paths through a grid with obstacles, setting blocked cells to zero.Practice · medium · LeetCodeSubarray sum equals KCount the subarrays whose sum is exactly k, even with negative numbers, using prefix sums and a hash map.

Asked in interviews

Something wrong with this lesson? Report a problem