Counting
nPr = n! / (n-r)! nCr = n! / (r!(n-r)!)
repeats = n! / (a! b! c!) e.g. COOKIE = 6!/2! = 360
circular = (n-1)!
stars & bars = C(n+k-1, k-1) n identical items into k boxes
- Adjacent/together: glue into one block → count block as 1 letter → multiply by internal arrangements
- Never adjacent: total − adjacent
- Derangements: D(3)=2, D(4)=9, D(5)=44
- BOOLEAN (7 letters, 2 O's): total 7!/2!=2520; O's adjacent=6!=720; never adjacent=1800
Probability
P(A|B) = P(A∩B) / P(B)
P(at least one) = 1 - P(none)
E[X+Y] = E[X] + E[Y] (linearity, always)
- "Given that…" = shrink the sample space first. Two dice given at least one 6: 11 outcomes → P(both 6) = 1/11
- Small cases: just list outcomes. n coins = 2^n, 2 dice = 36
- 3 coins, ≥2 Heads: {HHH, HHT, HTH, THH} = 4 → P(all 3) = 1/4
Modular Arithmetic
- Reduce the base first (7 mod 5 = 2), then find the cycle of powers, reduce exponent by cycle length
- 7^2026 mod 5: 7≡2, cycle 2,4,3,1 (len 4), 2026 mod 4=2 → 2²=4 ✓
Last-digit cycles (mod 10):
2: 2 4 8 6 3: 3 9 7 1 7: 7 9 3 1
4: 4 6 9: 9 1 0,1,5,6: fixed
- Fermat: a^(p-1) ≡ 1 (mod p) when p is prime and p∤a
- Div by 3 or 9: digit sum. By 4: last 2 digits. By 11: alternating digit sum
Sets & Pigeonhole
|A∪B| = |A| + |B| - |A∩B|
|A∪B∪C| = sum singles - sum pairs + triple
neither = total - |A∪B|
Pigeonhole: to guarantee k in one box with m boxes → m*(k-1)+1
- 3 in same day of week: 7 days × 2 + 1 = 15
- 3 in same month: 12 × 2 + 1 = 25
Recurrences & Complexity
T(n) = T(n/2) + 1 → O(log n)
T(n) = T(n/2) + n → O(n)
T(n) = 2T(n/2) + n → O(n log n) ← merge sort
T(n) = T(n-1) + 1 → O(n)
T(n) = T(n-1) + n → O(n²)
T(n) = 2T(n-1) + 1 → O(2^n)
For small n just unroll by hand: T(1)=1, T(3)=3T(1)+3=6, T(9)=3×6+9=27
Graphs & Sums
sum of degrees = 2 × edges (handshake lemma)
tree n nodes = n-1 edges
K_n complete = n(n-1)/2 edges
k-regular on n vertices = nk/2 edges
1+2+…+n = n(n+1)/2
1²+…+n² = n(n+1)(2n+1)/6
2^10=1024 2^16=65536 2^20≈1M 2^30≈1G
Exam Tricks
- Four options → cross out the absurd two first
- Words like "always", "only", "never" → usually wrong
- Longest, most detailed option in a conceptual question → often right
- For math → plug in n=2 or 3 to test each option
Files & Navigation
ls -la list all, long cd - previous dir
pwd current dir mkdir -p a/b/c
cp -r src dst copy dir mv a b move/rename
rm -rf dir force delete touch f create/update time
cat f print less f scroll
head -n 5 f first 5 tail -n 5 last 5
wc -l f count lines (-w words, -c bytes)
du -sh * size of items df -h disk free
ln -s tgt lnk symlink (hard link: no -s)
- Soft link = pointer to path, breaks if target deleted. Hard link = same inode, survives.
- Key dirs:
/etc config · /var/log logs · /tmp temp · /proc process info · /boot kernel
find
find /etc -name "config.yaml" by name (-iname case-insensitive)
find . -type f files only (-type d = dirs)
find /var/log -mtime -1 modified LESS than 1 day ago
find /var/log -mtime +1 modified MORE than 1 day ago
find . -size +10M bigger than 10 MB
find . -perm 755 exact permissions
find . -name "*.log" -exec rm {} \; run command on each
Trap: -mtime -1 = newer than 1 day · -mtime +1 = older than 1 day
grep
grep "txt" f match grep -i ignore case
grep -r "txt" . recursive grep -n show line numbers
grep -v "txt" f INVERT grep -c count matching lines
grep -l only filenames grep -w whole word
grep -E "a|b" regex OR grep -A2 -B2 2 lines after/before
Redirection & Pipes
> overwrite >> append
< read from file | pipe
2> stderr 2>&1 stderr → where stdout goes
&> both to file /dev/null black hole
tee f write AND show on screen
cmd > out.txt 2>&1 both stdout+stderr into out.txt
cmd 2>&1 > out.txt NOT the same: stderr still on terminal
cmd > out.txt 2>/dev/null stdout to file, errors discarded
- FDs: 0=stdin, 1=stdout, 2=stderr.
2>&1 → "same place as fd 1"
&& run if prev succeeded · || only if failed · ; always · $? last exit code
Permissions
r=4 w=2 x=1
chmod 754 → rwx r-x r--
chmod 755 → rwx r-x r-x chmod 644 → rw- r-- r--
chmod 600 → rw- --- --- chmod 640 → rw- r-- ---
chmod 777 → rwx rwx rwx
ls -l first char: - file · d dir · l symlink
- Special: setuid 4000, setgid 2000, sticky 1000 (only owner can delete in /tmp)
- Execute on a directory = permission to
cd into it
umask 022 → new files 644, new dirs 755
Processes & Signals
ps aux / ps -ef all procs top / htop live
kill 1234 SIGTERM (15) kill -9 SIGKILL
Ctrl+C = SIGINT(2) Ctrl+Z = SIGTSTP Ctrl+D = EOF
SIGHUP 1 SIGINT 2 SIGKILL 9 SIGSEGV 11 SIGTERM 15
SIGKILL & SIGSTOP can NEVER be caught or ignored
- Zombie (Z): finished, parent never called
wait(). Can't kill it—fix the parent.
- Orphan: parent died first → adopted by PID 1 (init/systemd)
fork() returns 0 in child, child's PID in parent, −1 on failure
Networking
MAC=48bit IPv4=32bit IPv6=128bit
usable hosts /n = 2^(32-n) - 2 /24=254 /26=62 /30=2
private: 10.0.0.0/8 172.16.0.0/12 192.168.0.0/16
ports: FTP 21 SSH 22 SMTP 25 DNS 53 HTTP 80 HTTPS 443
- TCP: connection-oriented, ordered, reliable, 3-way handshake SYN→SYN-ACK→ACK
- UDP: connectionless, no guarantee (DNS, video, games)
- ARP: IP→MAC · DHCP: assigns IPs · DNS: name→IP · NAT: private→public
- OSI: 1 Physical · 2 Data Link (MAC, switch) · 3 Network (IP, router) · 4 Transport (TCP/UDP) · 7 Application
Constraint → Complexity
| Constraint on n | Target | Approach |
| n ≤ 10 | O(n!) / O(2^n) | Brute force, backtracking |
| n ≤ 100 | O(n³–n⁴) | Triple loops, grid brute force |
| n ≤ 1 000 | O(n²) | Double loop, naive simulation |
| n ≤ 2·10⁵ | O(n log n) | Hashmap, prefix, sort, stack |
| n ≤ 10⁹ | O(√n) / O(log n) | Formula / math observation |
| n ≤ 10¹⁸ | O(1) / O(log n) | Formula only. Loop = TLE |
| n ≤ 10^1000 | digit work | Never int(), work on chars |
Python speed: ~10^7 simple ops/sec. 1s limit ≈ 10^7 iterations.
Fast I/O Template
import sys
input = sys.stdin.readline
n = int(input())
n, k = map(int, input().split())
a = list(map(int, input().split()))
# Or read everything at once:
data = list(map(int, sys.stdin.buffer.read().split()))
n, k = data[0], data[1]
a = data[2:2+n]
# Output: never print() in a 10^5 loop
print("\n".join(map(str, ans)))
Python Gotchas
// floor div: -7//2 == -4. % never negative for positive modulus.
- Ints are unbounded — no overflow. 10^1000 fits but a loop over it doesn't.
pow(a, b, m) — fast modular exponentiation.
math.isqrt(n) — exact integer sqrt. Never use n**0.5 for exact checks.
math.gcd, math.lcm, math.comb(n,r), math.factorial
s.lstrip("0") or "0" — strip leading zeros safely
- Building a string with
+= in a loop = O(n²). Use a list and join.
sys.setrecursionlimit(10**6) for deep recursion; prefer iteration.
Essential Patterns
Prefix sum + hashmap (subarray count)
count = defaultdict(int)
count[0] = 1 # ← seed for empty prefix
prefix = 0
for x in a:
prefix = (prefix + x) % m
ans += count[prefix]
count[prefix] += 1
Sliding window (fixed size k)
current = sum(a[:k]); best = current; best_i = 0
for i in range(k, len(a)):
current += a[i] - a[i-k]
if current < best: # strict < for leftmost
best = current; best_i = i-k+1
Monotonic stack (remove k digits → smallest)
stack = []
for digit in s:
while k > 0 and stack and stack[-1] > digit:
stack.pop(); k -= 1
stack.append(digit)
if k: stack = stack[:-k]
result = "".join(stack).lstrip("0") or "0"
Counting multiples (inclusion-exclusion)
# Divisible by exactly one of a or b up to n:
ans = n//a + n//b - 2*(n//lcm(a,b))
Complexity Quick Ref
| Complexity | Example | n=100 000 |
| O(1) | Formula | ✅ Excellent |
| O(log n) | Binary search | ✅ Excellent |
| O(n) | Single pass | ✅ Excellent |
| O(n log n) | Sort | ✅ Fine |
| O(n²) | Nested loops | ⚠️ Slow |
| O(n³) | Triple nested | ❌ TLE |
Problem Type Catalogue
| You see | It is |
| count numbers up to 10^18 satisfying… | inclusion–exclusion / formula |
| sum 1−2+3… n up to 10^9 | pair-up closed form |
| huge number as string | digit/greedy logic on chars |
| how many subarrays with… | prefix sum + hashmap |
| subarray of size k min/max | fixed sliding window |
| q range updates → final array | difference array (or naive if tiny) |
| smallest/largest after removing k digits | monotonic stack |
| grid n,m≤100, count squares/patterns | brute force + early exit |
| repeat until reaches 1/0 | simulation, watch for cycles |
| minimum value such that… | binary search on answer |
| T tests each tiny | O(1)/O(log) per test + fast IO |
| pairs (i,j) with i<j | hashmap counting / two pointers |
Alternating Sum Formula
+1 −2 +3 −4 … up to n terms:
- Pair: (1−2)+(3−4)+… each pair = −1
- n even → answer = −n/2
- n odd → answer = (n+1)/2
pairs = n // 2
remainder = n % 2
ans = -pairs + (n if remainder else 0)
Diagonal Pattern in a Grid
- Main diagonal of k×k at (r,c): cells (r+t, c+t) for t in 0..k-1
- Anti-diagonal: cells (r+t, c+k-1-t)
- Pattern "X" in k×k: diagonals = 1, rest = 0. Total 1s = 2k−1.
- n,m ≤ 100 → brute force each window, early-exit on first mismatch.
Bit Tricks
x & 1 parity (0=even, 1=odd)
x >> 1 floor divide by 2
1 << k 2^k
x > 0 and x&(x-1)==0 power of 2?
x & -x lowest set bit
a ^ a = 0, a ^ 0 = a XOR: finds the single element
bin(x).count("1") popcount
Key DSA Facts for MCQs
| Topic | Key fact |
| BST worst case | Skewed = O(n), not O(log n) |
| Merge Sort | Always O(n log n), stable |
| Quick Sort worst | O(n²) on sorted/reverse input |
| Call stack structure | Stack (LIFO) |
| Starvation risk | SRTF (Shortest Remaining Time First) |
| In-order BST | Gives sorted order |
| Row-major speed | Cache locality in C/Python |
| Paging eliminates | External fragmentation (not internal) |
| SIGKILL | Cannot be caught, blocked or ignored |
| SQL HAVING | Filters groups (after GROUP BY); WHERE filters rows |
| 2NF | Removes partial dependencies (non-key on part of composite PK) |
| PUT vs POST | PUT = idempotent, not safe; POST = neither |
| CSRF | Exploits browser cookie auto-send to forge requests |