DSA Math Formula Cheat Sheet (with Usage &
Description)
1. Sum of First N Natural Numbers
Formula: n(n+1)/2
Used for: Missing number problems, sum of array from 1 to N, arithmetic progression based
questions.
2. Sum of Squares
Formula: n(n+1)(2n+1)/6
Used for: Mathematical derivations, problems involving square sums or range calculations.
3. GCD (Euclidean Algorithm)
Formula: gcd(a, b) = gcd(b, a % b)
Used for: Finding greatest common divisor, number theory problems, array divisibility logic.
4. LCM Relation
Formula: LCM(a, b) * GCD(a, b) = a * b
Used for: LCM based problems, scheduling cycles, repeating pattern questions.
5. Binary Search Mid Formula
Formula: mid = low + (high - low) / 2
Used for: Binary search implementation to avoid integer overflow.
6. Prefix Sum
Formula: prefix[i] = prefix[i-1] + arr[i]
Used for: Range sum queries, subarray sum problems, optimization from O(n^2) to O(n).
7. Range Sum using Prefix
Formula: sum(l, r) = prefix[r] - prefix[l-1]
Used for: Efficient subarray sum calculation.
8. Sliding Window Update
Formula: window_sum = window_sum + arr[right] - arr[left]
Used for: Fixed size window problems like max sum subarray of size k.
9. Power of Two Check (Bit Manipulation)
Formula: n > 0 && (n & (n-1)) == 0
Used for: Checking if number is power of 2, optimization in bit problems.
10. Remove Last Set Bit
Formula: n & (n-1)
Used for: Bit manipulation, counting set bits efficiently.
11. Count Set Bits Logic
Formula: while(n>0){ n = n & (n-1); count++; }
Used for: Efficient bit counting problems.
12. Fibonacci Recurrence
Formula: F(n) = F(n-1) + F(n-2)
Used for: Recursion, dynamic programming, sequence pattern problems.
13. Total Subarrays
Formula: n(n+1)/2
Used for: Counting total subarrays in array related combinatorics problems.
14. Total Subsequences
Formula: 2^n
Used for: Subset, subsequence, and backtracking problems.
15. Combination Formula (nCr)
Formula: n! / (r! * (n-r)!)
Used for: Combinatorics, subset count, arrangement & selection problems.
16. Modulo Arithmetic Rules
Formula: (a+b)%m=(a%m+b%m)%m, (a*b)%m=(a%m*b%m)%m
Used for: Large number handling, competitive programming constraints.
17. Fast Exponentiation
Logic: if n even → (a^(n/2))^2, if odd → a * a^(n-1)
Used for: Power calculations in logarithmic time (O(log n)).
18. Geometric Series Sum
Formula: a(1 - r^n)/(1 - r)
Used for: Recursion tree analysis, exponential growth pattern problems.
19. Time Complexity Growth Order
Order: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)
Used for: Comparing algorithm efficiency during optimization.
20. Missing Number Formula
Formula: n(n+1)/2 - sum(array)
Used for: Finding missing number from 1 to N in O(n) time.