Master mathematical foundations essential for algorithmic problem-solving. Learn prime number algorithms, modular arithmetic, combinatorics, bit manipulation, and matrix exponentiation with complete C# implementations and 15+ interview-ready solutions.
Foundation concepts that appear in virtually every mathematical problem: integer overflow, modular arithmetic, and the C# Math class utilities.
C# integer types have fixed ranges. Understanding overflow is critical:
| Type | Min Value | Max Value | Size |
|---|---|---|---|
| byte | 0 | 255 | 8 bits |
| sbyte | -128 | 127 | 8 bits |
| int | -2,147,483,648 | 2,147,483,647 | 32 bits |
| long | -9,223,372,036,854,775,808 | 9,223,372,036,854,775,807 | 64 bits |
// Math class utilities public static void MathUtilities() { // Max and Min int max = Math.Max(10, 20); // 20 int min = Math.Min(10, 20); // 10 // Absolute value int abs = Math.Abs(-42); // 42 // Power and square root double power = Math.Pow(2, 10); // 1024 double sqrt = Math.Sqrt(16); // 4 // Rounding int ceil = (int)Math.Ceiling(3.2); // 4 int floor = (int)Math.Floor(3.9); // 3 } // Overflow detection public static bool WillOverflow(int a, int b) { // Check: a + b > int.MaxValue return b > int.MaxValue - a; } // Safe addition with long public static long SafeAdd(long a, long b) { if (b > long.MaxValue - a) throw new OverflowException(); return a + b; }
Key Points: Use Math.Max/Min for comparisons, Math.Abs for magnitude, Math.Pow/Sqrt for exponents and roots, Math.Ceiling/Floor for rounding. When adding/multiplying large numbers, use long or check bounds beforehand.
Modular arithmetic reduces large numbers and prevents overflow. The operation a % m gives remainder when dividing a by m.
Fundamental number theory operations with elegant recursive and iterative solutions. GCD via Euclidean algorithm is O(log n) and appears frequently in interview problems.
The most efficient GCD method. Based on: GCD(a, b) = GCD(b, a mod b), continuing until b = 0.
public static int GCD(int a, int b) { // Base case: when b is 0, GCD is a while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } // Example usage int result = GCD(48, 18); // Step 1: GCD(48, 18) -> a=48, b=18 // Step 2: a=18, b=48%18=12 -> GCD(18, 12) // Step 3: a=12, b=18%12=6 -> GCD(12, 6) // Step 4: a=6, b=12%6=0 -> GCD(6, 0) // Return 6
a mod b becomes smallerElegant recursive version of same algorithm:
public static int GCDRecursive(int a, int b) { if (b == 0) return a; return GCDRecursive(b, a % b); }
Least Common Multiple uses the identity: LCM(a, b) = (a Ć b) / GCD(a, b)
public static long LCM(long a, long b) { return (a / GCD((int)a, (int)b)) * b; } // Example: LCM(12, 18) // GCD(12, 18) = 6 // LCM = (12 / 6) * 18 = 2 * 18 = 36
Note: Use long to prevent overflow when multiplying a Ć b.
Finds integers x, y such that ax + by = GCD(a, b). Used in modular inverse calculations.
public static (int gcd, int x, int y) ExtendedGCD(int a, int b) { if (b == 0) return (a, 1, 0); var (gcd, x1, y1) = ExtendedGCD(b, a % b); int x = y1; int y = x1 - (a / b) * y1; return (gcd, x, y); }
Critical algorithms for identifying and generating primes. Trial division is O(ān), Sieve of Eratosthenes is O(n log log n) for range operations.
Basic primality test by checking divisibility up to ān. Optimization: only check odd numbers after 2.
public static bool IsPrime(int n) { if (n < 2) return false; if (n == 2) return true; if (n % 2 == 0) return false; // Check odd divisors up to sqrt(n) for (int i = 3; i * i <= n; i += 2) { if (n % i == 0) return false; } return true; }
Efficiently find all primes up to n. Mark multiples of each prime as composite. O(n log log n) - much faster than checking each number individually.
public static bool[] SieveOfEratosthenes(int n) { bool[] isPrime = new bool[n + 1]; for (int i = 2; i <= n; i++) isPrime[i] = true; // Sieve: mark multiples of each prime as composite for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { // Mark all multiples of i as not prime for (int j = i * i; j <= n; j += i) isPrime[j] = false; } } return isPrime; } // Example: find all primes up to 30 bool[] primes = SieveOfEratosthenes(30); // Result: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
For very large ranges [L, R] where R - L is small but R is huge, sieve only the range segment. Find small primes up to āR first, then eliminate their multiples in [L, R].
Operations with remainders. Crucial for preventing overflow and solving cyclic/periodic problems. Master (a+b)%m, (aĆb)%m, modular exponentiation, and modular inverse.
Properties of modulo:
| Property | Formula | Example (mod 7) |
|---|---|---|
| Addition | (a + b) % m = ((a % m) + (b % m)) % m | (5 + 8) % 7 = (5 + 1) % 7 = 6 |
| Multiplication | (a Ć b) % m = ((a % m) Ć (b % m)) % m | (6 Ć 5) % 7 = (6 Ć 5) % 7 = 2 |
| Subtraction | (a - b) % m = ((a % m) - (b % m) + m) % m | (3 - 8) % 7 = (-5 + 7) % 7 = 2 |
| Power | a^b % m = (a % m)^b % m | 2^10 % 7 = 4 |
Compute a^b mod m efficiently in O(log b) using binary exponentiation. Prevents overflow and computation time explosion.
public static long ModPow(long a, long b, long m) { long result = 1; a %= m; while (b > 0) { // If b is odd, multiply result by a if ((b & 1) == 1) result = (result * a) % m; // Square a and halve b a = (a * a) % m; b >>= 1; } return result; } // Example: 2^10 mod 1000000007 long ans = ModPow(2, 10, 1000000007); // 1024
Key Insight: Binary exponentiation splits b into powers of 2. If b = 1010ā = 8+2, then a^b = a^8 Ć a^2. Only O(log b) multiplications needed.
Find x such that (a Ć x) ā” 1 (mod m). Exists only when gcd(a, m) = 1. Use Fermat's Little Theorem or Extended GCD.
// Method 1: Using Fermat's Little Theorem // If m is prime: a^(-1) ā” a^(m-2) (mod m) public static long ModInverse(long a, long m) { return ModPow(a, m - 2, m); } // Method 2: Using Extended GCD (works for any coprime a, m) public static long ModInverseGCD(long a, long m) { var (gcd, x, y) = ExtendedGCD((int)a, (int)m); if (gcd != 1) return -1; // No inverse exists return (x % m + m) % m; }
Count arrangements and selections. Factorials, binomial coefficients (nCr), Pascal's Triangle. Critical for permutation/combination problems.
nCr = n! / (r! Ć (n-r)!) = number of ways to choose r items from n items.
private const long MOD = 1000000007; private long[] fact, inv_fact; public void PrecomputeFactorials(int maxN) { fact = new long[maxN + 1]; inv_fact = new long[maxN + 1]; // Compute factorials fact[0] = 1; for (int i = 1; i <= maxN; i++) fact[i] = (fact[i - 1] * i) % MOD; // Compute inverse factorials using Fermat's Little Theorem inv_fact[maxN] = ModPow(fact[maxN], MOD - 2, MOD); for (int i = maxN - 1; i >= 0; i--) inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD; } public long NCr(int n, int r) { if (r > n || r < 0) return 0; return (fact[n] * inv_fact[r] % MOD) * inv_fact[n - r] % MOD; }
For small queries: Use Pascal's Triangle approach. For large n: Precompute factorials and inverse factorials using Fermat's Little Theorem (when MOD is prime).
Dynamic approach for nCr when n and r are bounded. nCr(n, r) = nCr(n-1, r-1) + nCr(n-1, r)
public static long[][] PascalsTriangle(int n) { long[][] dp = new long[n + 1][]; for (int i = 0; i <= n; i++) { dp[i] = new long[i + 1]; dp[i][0] = dp[i][i] = 1; for (int j = 1; j < i; j++) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; } return dp; }
Expected value calculations, reservoir sampling, Fisher-Yates shuffle. Algorithms that rely on statistical properties.
E(X) = Ī£(x_i Ć P(x_i)). In many DSA problems, calculate average outcome across all possibilities.
Randomly select k items from a stream of unknown length, each item equally likely. Classic interview problem.
public int[] ReservoirSample(int[] stream, int k) { int[] reservoir = new int[k]; int n = stream.Length; // Fill reservoir with first k elements for (int i = 0; i < k; i++) reservoir[i] = stream[i]; var rand = new Random(); // For each element from k onwards for (int i = k; i < n; i++) { // Random index 0 to i (inclusive) int j = rand.Next(0, i + 1); // If j < k, replace element at j with stream[i] if (j < k) reservoir[j] = stream[i]; } return reservoir; }
Probability: Each element has k/n probability of being in final sample, regardless of position.
Uniformly randomize array elements in O(n) time. Every permutation equally likely.
public void Shuffle(int[] nums) { var rand = new Random(); for (int i = nums.Length - 1; i > 0; i--) { // Pick random j from 0 to i int j = rand.Next(0, i + 1); // Swap nums[i] and nums[j] int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }
Power checks, Hamming weight, trailing zeros. Low-level number properties crucial for optimization.
Efficient checks for special numbers using bit operations.
// Power of 2: A power of 2 has exactly one bit set // n & (n-1) == 0 for powers of 2 public static bool IsPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; } // Power of 3: Check if log_3(n) is integer public static bool IsPowerOfThree(int n) { if (n <= 0) return false; while (n % 3 == 0) n /= 3; return n == 1; } // Power of 4: Power of 2 AND (n-1) has only odd bits set public static bool IsPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && (n - 1) % 3 == 0; }
Count how many 1s in binary representation. Use Brian Kernighan's algorithm: n & (n-1) removes rightmost 1 bit.
// Brian Kernighan's Algorithm: O(# of set bits) public static int HammingWeight(uint n) { int count = 0; while (n > 0) { n &= n - 1; // Remove rightmost 1 bit count++; } return count; } // Alternative: Built-in (modern C#) int weight = System.Numerics.BitOperations.PopCount(42);
Count zeros at end of n! (determined by factors of 5). Formula: ān/5ā + ān/25ā + ān/125ā + ...
// Count trailing zeros in n! public static int TrailingZeros(int n) { int count = 0; for (long i = 5; i <= n; i *= 5) count += (int)(n / i); return count; } // Example: 5! = 120 (1 trailing zero), 10! = 3628800 (2 trailing zeros)
Solve recurrence relations in O(log n). Classic: compute nth Fibonacci number in O(log n) instead of O(n).
For Fibonacci: F(n) = F(n-1) + F(n-2), express as matrix multiplication and use fast exponentiation.
// Matrix multiplication for 2x2 matrices private long[][] Multiply(long[][] A, long[][] B, long mod) { long[][] C = new long[2][]; C[0] = new long[2]; C[1] = new long[2]; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod; } } return C; } // Matrix exponentiation private long[][] MatPow(long[][] matrix, long n, long mod) { long[][] result = new long[][] { new long[] { 1, 0 }, new long[] { 0, 1 } }; while (n > 0) { if ((n & 1) == 1) result = Multiply(result, matrix, mod); matrix = Multiply(matrix, matrix, mod); n >>= 1; } return result; } // nth Fibonacci: F(n) = matrix^n [0][1] public static long Fibonacci(long n, long mod) { if (n == 0) return 0; if (n == 1) return 1; long[][] matrix = new long[][] { new long[] { 1, 1 }, new long[] { 1, 0 } }; long[][] result = MatPow(matrix, n, mod); return result[0][1]; }
Distance, line intersection, convex hull concepts. Practical geometry operations for coding interviews.
Euclidean distance: sqrt((x2-x1)Ā² + (y2-y1)Ā²). Often work with squared distance to avoid floating point.
// Euclidean distance (with sqrt) public static double Distance(double x1, double y1, double x2, double y2) { double dx = x2 - x1; double dy = y2 - y1; return Math.Sqrt(dx * dx + dy * dy); } // Squared distance (faster, avoids floating point) public static long DistanceSquared(int x1, int y1, int x2, int y2) { long dx = x2 - x1; long dy = y2 - y1; return dx * dx + dy * dy; }
Cross product determines orientation (clockwise/counterclockwise). Essential for line segment intersection.
// Cross product of vectors OA and OB public static long CrossProduct(int ox, int oy, int ax, int ay, int bx, int by) { return (long)(ax - ox) * (by - oy) - (long)(ay - oy) * (bx - ox); } // Check if point P lies on segment AB public static bool OnSegment(int ax, int ay, int bx, int by, int px, int py) { return px >= Math.Min(ax, bx) && px <= Math.Max(ax, bx) && py >= Math.Min(ay, by) && py <= Math.Max(ay, by); } // Convex Hull concept: Graham Scan approach // Not implementing full here due to complexity, but key is // sorting by polar angle and maintaining monotonic chain
15+ interview problems covering all math topics. Each includes complete, production-ready code.
public class Solution { public int CountPrimes(int n) { if (n <= 2) return 0; bool[] isPrime = new bool[n]; for (int i = 2; i < n; i++) isPrime[i] = true; for (int i = 2; i * i < n; i++) { if (isPrime[i]) { for (int j = i * i; j < n; j += i) isPrime[j] = false; } } int count = 0; for (int i = 2; i < n; i++) if (isPrime[i]) count++; return count; } }
public class Solution { public bool IsPowerOfThree(int n) { if (n <= 0) return false; while (n % 3 == 0) n /= 3; return n == 1; } }
public class Solution { public int TrailingZeroes(int n) { int count = 0; for (long i = 5; i <= n; i *= 5) count += (int)(n / i); return count; } }
public class Solution { private int GetNext(int n) { int sum = 0; while (n > 0) { int digit = n % 10; sum += digit * digit; n /= 10; } return sum; } public bool IsHappy(int n) { int slow = n, fast = GetNext(n); while (fast != 1 && slow != fast) { slow = GetNext(slow); fast = GetNext(GetNext(fast)); } return fast == 1; } }
public class Solution { public int TitleToNumber(string columnTitle) { int result = 0; foreach (char c in columnTitle) { result = result * 26 + (c - 'A' + 1); } return result; } }
public class Solution { public int RomanToInt(string s) { var romanValues = new Dictionary<char, int> { { 'I', 1 }, { 'V', 5 }, { 'X', 10 }, { 'L', 50 }, { 'C', 100 }, { 'D', 500 }, { 'M', 1000 } }; int total = 0; for (int i = 0; i < s.Length; i++) { int val = romanValues[s[i]]; if (i + 1 < s.Length && val < romanValues[s[i + 1]]) total -= val; else total += val; } return total; } } // Problem 7: Integer to Roman (LeetCode 12)
public class Solution { public string IntToRoman(int num) { int[] values = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 }; string[] symbols = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" }; StringBuilder sb = new StringBuilder(); for (int i = 0; i < values.Length; i++) { while (num >= values[i]) { sb.Append(symbols[i]); num -= values[i]; } } return sb.ToString(); } } // Problem 8: Sqrt(x) (LeetCode 69) - Newton's Method
public class Solution { // Method 1: Newton's Method (faster convergence) public int MySqrt(int x) { if (x == 0) return 0; long result = x; while (result * result > x) { result = (result + x / result) / 2; } return (int)result; } // Method 2: Binary Search public int MySqrtBinary(int x) { long left = 0, right = x; while (left <= right) { long mid = left + (right - left) / 2; long sq = mid * mid; if (sq == x) return (int)mid; else if (sq < x) left = mid + 1; else right = mid - 1; } return (int)right; } } // Problem 9: Pow(x, n) (LeetCode 50) - Fast Exponentiation
public class Solution { public double MyPow(double x, int n) { long N = n; if (N < 0) { x = 1 / x; N = -N; } double result = 1; double base_val = x; while (N > 0) { if ((N & 1) == 1) result *= base_val; base_val *= base_val; N >>= 1; } return result; } }
public class Solution { public IList<string> FizzBuzz(int n) { var result = new List<string>(); for (int i = 1; i <= n; i++) { bool fizz = (i % 3 == 0); bool buzz = (i % 5 == 0); if (fizz && buzz) result.Add("FizzBuzz"); else if (fizz) result.Add("Fizz"); else if (buzz) result.Add("Buzz"); else result.Add(i.ToString()); } return result; } }
public class Solution { public string AddBinary(string a, string b) { StringBuilder sb = new StringBuilder(); int carry = 0; int i = a.Length - 1; int j = b.Length - 1; while (i >= 0 || j >= 0 || carry > 0) { int sum = carry; if (i >= 0) sum += a[i--] - '0'; if (j >= 0) sum += b[j--] - '0'; sb.Append(sum % 2); carry = sum / 2; } char[] result = sb.ToString().ToCharArray(); System.Array.Reverse(result); return new string(result); } }
public class Solution { public string Multiply(string num1, string num2) { if (num1 == "0" || num2 == "0") return "0"; int[] result = new int[num1.Length + num2.Length]; int i = num1.Length - 1; int j = num2.Length - 1; for (; i >= 0; i--) { for (int k = j; k >= 0; k--) { int mul = (num1[i] - '0') * (num2[k] - '0'); int p1 = i + k, p2 = i + k + 1; int sum = mul + result[p2]; result[p2] = sum % 10; result[p1] += sum / 10; } } StringBuilder sb = new StringBuilder(); foreach (int digit in result) if (!(sb.Length == 0 && digit == 0)) sb.Append(digit); return sb.Length == 0 ? "0" : sb.ToString(); } }
public class Solution { private int[] prefixSum; private Random rand; public Solution(int[] w) { prefixSum = new int[w.Length]; rand = new Random(); prefixSum[0] = w[0]; for (int i = 1; i < w.Length; i++) prefixSum[i] = prefixSum[i - 1] + w[i]; } public int PickIndex() { int target = rand.Next(1, prefixSum[prefixSum.Length - 1] + 1); return BinarySearch(target); } private int BinarySearch(int target) { int left = 0, right = prefixSum.Length - 1; while (left < right) { int mid = left + (right - left) / 2; if (prefixSum[mid] < target) left = mid + 1; else right = mid; } return left; } }
public class Solution { private int[] original; private Random rand; public Solution(int[] nums) { original = (int[])nums.Clone(); rand = new Random(); } public int[] Shuffle() { int[] result = (int[])original.Clone(); for (int i = result.Length - 1; i > 0; i--) { int j = rand.Next(0, i + 1); int temp = result[i]; result[i] = result[j]; result[j] = temp; } return result; } public int[] Reset() { return (int[])original.Clone(); } }
public class Solution { public int NthUglyNumber(int n) { int[] dp = new int[n]; dp[0] = 1; int i2 = 0, i3 = 0, i5 = 0; for (int i = 1; i < n; i++) { int next2 = dp[i2] * 2; int next3 = dp[i3] * 3; int next5 = dp[i5] * 5; int nextUgly = Math.Min(next2, Math.Min(next3, next5)); dp[i] = nextUgly; if (nextUgly == next2) i2++; if (nextUgly == next3) i3++; if (nextUgly == next5) i5++; } return dp[n - 1]; } }
public class Solution { public int FindNthDigit(int n) { long digitCount = 1; // 1-digit: 1..9 (9 numbers) long startNum = 1; long countInRange = 9; // Find which range (1-digit, 2-digit, etc.) contains nth digit while (n > digitCount * countInRange) { n -= (int)(digitCount * countInRange); digitCount++; startNum *= 10; countInRange *= 10; } // Find which number and which digit within that number long num = startNum + (n - 1) / digitCount; int digitIndex = (int)((n - 1) % digitCount); return int.Parse(num.ToString()[digitIndex].ToString()); } }
Patterns and shortcuts that accelerate problem-solving in coding interviews.
| Pattern | Technique | Example |
|---|---|---|
| Divisibility by power of 2 | Use bit operations (& with mask) | n & (n-1) == 0 for power of 2 |
| Modulo arithmetic safety | Take modulo before multiplying | (a % m) * (b % m) % m |
| Large exponents | Always use binary exponentiation | O(log n) instead of O(n) |
| Factorial modulo | Precompute factorials + inverse factorials | O(n) setup, O(1) queries |
| Cycle detection | Floyd's cycle detection (tortoise/hare) | Happy Number, Linked List Cycle |
| Prefix sum tricks | Cumulative sum for range queries | Random pick with weight |
long, check bounds, or take modulo early.// Safe multiplication: check before multiplying public static long SafeMultiply(long a, long b, long limit) { if (a > limit / b) throw new OverflowException(); return a * b; } // Safe addition: check before adding public static long SafeAdd(long a, long b) { if (a > long.MaxValue - b) throw new OverflowException(); return a + b; }
When comparing floating point numbers, use epsilon tolerance instead of exact equality:
public static bool AlmostEqual(double a, double b, double epsilon = 1e-9) { return Math.Abs(a - b) < epsilon; }
Strategic approaches to identify and solve mathematical problems in live coding interviews.
long, modulo, or check bounds. Better safe than wrong.n & (n-1), toggle with XOR, etc.Prepare these before interviews to save time: