Here are some of the useful functions to help you with LeetCode contests. Some of them have ideas based on Algorithms for Competitive Programming.
Table of Content
-
Calculate nCr using Modular Multiplicative Inverse
-
Example Template
1. Calculate nCr using Modular Multiplicative Inverse
nCr is calculated as: $nCr = \frac{n!}{(n-r)! \, r!}$
To avoid the issues associated with large number operations and potential rounding errors when computing $n!$ divided by $(n-r)!$ and $r!$, we instead convert the divisions into multiplications using the concept of the Modular Multiplicative Inverse. Specifically, the combination $nCr$ is computed as:
$nCr = n! \times \text{inv}((n-r)!) \times \text{inv}(r!)$
where $\text{inv}(a!)$ represents the modular inverse of $a!$.
1.1. Example Code
Constant MOD is set to $1{,}000{,}000{,}007$, a large prime number frequently used in competitive programming and algorithm design to avoid integer overflow and to guarantee the existence of modular inverses for any integer that is relatively prime to the modulus. The arrays fact and invFact are used to store the factorial values and their corresponding modular inverses, respectively.
private int MOD = 1_000_000_007;
private long[] fact, invFact;
The following code snippet initializes a modular exponentiation function designed to compute $\text{base}^{\text{exp}}$ modulo a given modulus. This function operates in $O(\log(\text{exp}))$ ~ $O(\log(\text{N}))$ time complexity, which is achieved by repeatedly halving the exponent at each iteration (using the operation exp >>= 1).
private long modPow(long base, int exp, int mod) {
long result = 1;
while (exp > 0) {
if ((exp & 1) == 1) result = result * base % mod;
base = base * base % mod;
exp >>= 1;
}
return result;
}
According to Fermat’s Little Theorem, for a prime number $p$, the expression $a^p - a$ is divisible by $p$. Building on this principle, we can derive that the difference $a^{p-2} - a^{-1}$ is likewise divisible by $p$. We first build the factorials. Then, we can build the inverse factorials starting with $\text{inv}(n!) = n!^{MOD-2}$ mod MOD.
private void buildFactorials(int n) {
fact = new long[n+1];
invFact = new long[n+1];
fact[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % MOD;
invFact[n] = modPow(fact[n], MOD-2, MOD);
for (int i = n-1; i >= 0; i--) invFact[i] = invFact[i+1] * (i+1) % MOD;
}
Based on the factorials and the inverse factorials calculated above, we are now able to calculate nCr:
private long nCr(int r, int n) {
if (r < 0 || r > n) return 0;
return (fact[n] * invFact[r] % MOD) * invFact[n-r] % MOD;
}
1.2. Exercises
2. Example Template
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) throws Exception {
// FastScanner io = new FastScanner("");
FastScanner io = new FastScanner();
int t = 1; // t = io.nextInt();
while (t > 0) {
t--;
}
io.close();
}
/**
RESERVED INSTANCES
*/
static final int mod = 1_000_000_007; // prime number
static final long oo = (long) 2e18; // infinity number
static final Random random = new Random();
/**
HELPER
https://tinyurl.com/lamng3-code
*/
// ALGEBRA
static long add(long a, long b) { return (a + b) % mod; }
static long subtract(long a, long b) { return ((a - b) % mod + mod) % mod; }
static long multiply(long a, long b) { return (a * b) % mod; }
static long exp(long base, long exp) {
long result = 1;
while (exp > 0) {
if ((exp & 1) == 1) result = multiply(result, base);
base = multiply(base, base);
exp >>=1;
}
return result;
}
// NUMBER THEORY
static int gcd(int a, int b) {
while (b > 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
static int lcm(int a, int b) { return a * b / gcd(a,b); }
// ARRAY OPERATIONS
static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; }
static void shuffle(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
int ri = random.nextInt(n); // random index
swap(a, i, ri);
}
}
// SORTING
static void sort(int[] a) { Arrays.sort(a); }
static void sort(long[] a) { Arrays.sort(a); }
static <T extends Comparable<? super T>> void sort(List<T> a) { Collections.sort(a); }
static void ruffle_sort(int[] a) { shuffle(a); sort(a); }
// FACTORIALS & nCk
static long[] factorials = new long[2_000_005];
static long[] inverseFactorials = new long[2_000_005];
static void precompute_factorials() {
int n = factorials.length;
factorials[0] = 1;
for (int i = 1; i < factorials.length; i++) {
factorials[i] = multiply(factorials[i-1], i);
}
inverseFactorials[n-1] = exp(factorials[n-1], mod-2);
for (int i = n-2; i >= 0; i--) {
inverseFactorials[i] = multiply(inverseFactorials[i=1], i);
}
}
static long nCk(int n, int k) {
return multiply(factorials[n], multiply(inverseFactorials[n-k], inverseFactorials[k]));
}
/**
DATA STRUCTURES
*/
static class MultiSet {
static TreeMap<Integer, Integer> multiset;
public MultiSet() { multiset = new TreeMap<>(); }
static void add(int x) {
multiset.putIfAbsent(x, 0);
multiset.put(x, multiset.get(x)+1);
}
static void remove(int x) {
multiset.putIfAbsent(x, 0);
multiset.put(x, multiset.get(x)-1);
if (multiset.get(x) <= 0) multiset.remove(x);
}
}
/**
IO
*/
static class FastScanner extends PrintWriter {
private BufferedReader br;
private StringTokenizer st;
// standard input
public FastScanner() { this(System.in, System.out); }
public FastScanner(InputStream i, OutputStream o) {
super(o);
st = new StringTokenizer("");
br = new BufferedReader(new InputStreamReader(i));
}
// USACO-style file input
public FastScanner(String problemName) throws IOException {
super(problemName + ".out");
st = new StringTokenizer("");
br = new BufferedReader(new FileReader(problemName + ".in"));
}
// returns null if no more input
public String next() {
try {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
} catch (Exception e) { }
return null;
}
public int nextInt() { return Integer.parseInt(next()); }
public double nextDouble() { return Double.parseDouble(next()); }
public long nextLong() { return Long.parseLong(next()); }
}
}
Sign-off
Congratulations on making it this far! Best of luck in your future competitions!