Mathematics for DSA
The logarithm rules, sums, number representations, modular arithmetic, GCD, primes, counting and bit operations that later modules rely on — each with a small verified program.
What you will learn
The logarithm rules, sums, number representations, modular arithmetic, GCD, primes, counting and bit operations that later modules rely on — each with a small verified program.
Prerequisites: Module 2.
3.1 Logarithms and exponentials
Rules: log(ab)=log a+log b, log(a^k)=k log a, and logarithm bases differ only by a constant factor in asymptotic analysis.
log_b n = log_2 n / log_2 b, so O(log₂ n) and O(log₁₀ n) are the same class. Useful facts: 2¹⁰ = 1024 ≈ 10³, so log₂ 10⁶ ≈ 20 and log₂ 10⁹ ≈ 30 — binary search over a billion sorted values needs about 30 steps.
3.2 Summations
Arithmetic series, geometric series, harmonic series, and sums such as 1+2+...+n = n(n+1)/2.
Closed form / growth 1 + 2 + … + n n(n+1)/2 = Θ(n²) 1 + r + r² + … + r^k (r ≠ 1)
(r^(k+1) − 1)/(r − 1); for r = 2, 2^(k+1) − 1 1 + 1/2 + 1/3 + … + 1/n (harmonic) ln n + 0.5772… + o(1) = Θ(log n) 1² + 2² + … + n² n(n+1)(2n+1)/6 = Θ(n³)
3.3 Number systems and bit representation
Binary, decimal, hexadecimal, signed integers, two's complement, overflow, integer division, and safe conversion.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Signed overflow in C++ is undefined behaviour — the compiler may assume it never happens — so INT_MAX + 1 in int is a bug, not “wraps to INT_MIN”. Unsigned arithmetic wraps modulo 2^w by definition. Widen first (long long) when a sum or product can exceed the range.
#include <bits/stdc++.h>
using namespace std;
int main() {
int8_t x = -6;
cout << "-6 as 8-bit two's complement: " << bitset<8>(static_cast<uint8_t>(x)) << '\n';
cout << "~5 + 1 = " << (~5 + 1) << " (two's complement negation)\n";
cout << "INT_MAX = " << INT_MAX << ", INT_MIN = " << INT_MIN << '\n';
long long safe = static_cast<long long>(INT_MAX) + 1; // widen before adding
cout << "INT_MAX + 1 computed in long long: " << safe << '\n';
cout << "integer division truncates toward zero: 7/2=" << 7 / 2 << ", -7/2=" << -7 / 2
<< ", -7%2=" << -7 % 2 << '\n';
cout << "hex 0x" << hex << 255 << dec << " = 255, binary " << bitset<8>(255) << '\n';
unsigned u = 0;
cout << "unsigned wrap: 0u - 1 = " << (u - 1) << '\n';
}-6 as 8-bit two's complement: 11111010
~5 + 1 = -5 (two's complement negation)
INT_MAX = 2147483647, INT_MIN = -2147483648
INT_MAX + 1 computed in long long: 2147483648
integer division truncates toward zero: 7/2=3, -7/2=-3, -7%2=-1
hex 0xff = 255, binary 11111111
unsigned wrap: 0u - 1 = 42949672953.4 Modular arithmetic
For modulus m, normalize negative remainders where needed. Addition and multiplication can be performed modulo m; division requires a modular inverse and is not generally equivalent to ordinary division.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
The products stay below (10⁹+7)² < 9.3·10¹⁸, inside long long. Fermat's inverse works only for a prime modulus and a value not divisible by it; Module 48 covers the extended Euclidean algorithm for the general case.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1'000'000'007;
long long normalize(long long x) { return ((x % MOD) + MOD) % MOD; }
long long power(long long b, long long e) { // binary exponentiation, O(log e)
long long r = 1;
b = normalize(b);
while (e > 0) {
if (e & 1) r = r * b % MOD;
b = b * b % MOD;
e >>= 1;
}
return r;
}
int main() {
cout << "-7 % 5 in C++ = " << -7 % 5 << "; normalized mod 5 = " << ((-7 % 5) + 5) % 5 << '\n';
long long a = 123456789, b = 987654321;
cout << "(a*b) mod p = " << a % MOD * (b % MOD) % MOD << '\n';
long long inv3 = power(3, MOD - 2); // Fermat: 3^(p-2) is 3^-1 mod p (p prime)
cout << "inverse of 3 = " << inv3 << ", check 3*inv3 mod p = " << 3 * inv3 % MOD << '\n';
cout << "12/3 via inverse = " << 12 * inv3 % MOD << '\n';
cout << "but (10/3) mod p != (10 mod p)/3: " << 10 * inv3 % MOD << " vs " << 10 / 3 << '\n';
}-7 % 5 in C++ = -2; normalized mod 5 = 3
(a*b) mod p = 259106859
inverse of 3 = 333333336, check 3*inv3 mod p = 1
12/3 via inverse = 4
but (10/3) mod p != (10 mod p)/3: 333333339 vs 33.5 GCD, LCM, and Euclidean algorithm
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Time is O(log min(a,b)). Derive lcm(a,b) using a / gcd(a,b) * b to reduce overflow risk, while still checking range limits. Here a * b = 2.4·10¹⁹ would overflow long long, but a / gcd * b = 1.2·10¹⁰ fits. The algorithm works because gcd(a, b) = gcd(b, a mod b): any common divisor of a and b also divides a − qb.
#include <bits/stdc++.h>
using namespace std;
long long gcdValue(long long a, long long b) {
while (b != 0) {
long long r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
// dry run for gcd(252, 105)
long long a = 252, b = 105;
while (b != 0) {
cout << "gcd(" << a << ", " << b << ") -> remainder " << a % b << '\n';
long long r = a % b; a = b; b = r;
}
cout << "result " << a << '\n';
cout << "gcdValue(252, 105) = " << gcdValue(252, 105) << ", std::gcd = " << std::gcd(252, 105) << '\n';
long long x = 4'000'000'000LL, y = 6'000'000'000LL;
cout << "lcm(" << x << ", " << y << ") = " << x / gcdValue(x, y) * y << '\n';
cout << "gcd(0, 9) = " << gcdValue(0, 9) << ", gcd(9, 0) = " << gcdValue(9, 0) << '\n';
}gcd(252, 105) -> remainder 42
gcd(105, 42) -> remainder 21
gcd(42, 21) -> remainder 0
result 21
gcdValue(252, 105) = 21, std::gcd = 21
lcm(4000000000, 6000000000) = 12000000000
gcd(0, 9) = 9, gcd(9, 0) = 93.6 Prime numbers and factorization
Trial division through i <= n/i, sieve of Eratosthenes, segmented sieve, prime factorization, divisor count, and divisor sum.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
For n = Π pᵢ^eᵢ, the divisor count is Π (eᵢ + 1) and the divisor sum is Π (1 + pᵢ + … + pᵢ^eᵢ). Starting the inner sieve loop at i² is safe because smaller multiples were already crossed out by smaller primes.
#include <bits/stdc++.h>
using namespace std;
vector<int> sieve(int n) { // O(n log log n)
vector<bool> composite(n + 1, false);
vector<int> primes;
for (int i = 2; i <= n; ++i) {
if (composite[i]) continue;
primes.push_back(i);
for (long long j = 1LL * i * i; j <= n; j += i) composite[j] = true;
}
return primes;
}
vector<pair<long long, int>> factorize(long long n) { // trial division, O(sqrt n)
vector<pair<long long, int>> f;
for (long long i = 2; i <= n / i; ++i) { // i <= n/i avoids overflow of i*i
int e = 0;
while (n % i == 0) { n /= i; ++e; }
if (e) f.push_back({i, e});
}
if (n > 1) f.push_back({n, 1});
return f;
}
int main() {
auto p = sieve(50);
cout << "primes <= 50:";
for (int x : p) cout << ' ' << x;
cout << "\ncount of primes <= 1000000: " << sieve(1'000'000).size() << '\n';
long long n = 360;
auto f = factorize(n);
long long divisors = 1, sigma = 1;
cout << n << " =";
for (auto [q, e] : f) {
cout << ' ' << q << '^' << e;
divisors *= e + 1;
long long s = 1, pw = 1;
for (int k = 0; k <
…primes <= 50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
count of primes <= 1000000: 78498
360 = 2^3 3^2 5^1
number of divisors = 24, sum of divisors = 1170
factorize(999999000001) = 999999000001^13.7 Combinatorics
Factorials, permutations, combinations, Pascal's triangle, binomial coefficients, pigeonhole principle, inclusion-exclusion, and counting with constraints.
Permutations of k from n: n!/(n−k)!. Combinations: C(n, k) = n!/(k!(n−k)!).
Pascal's rule C(n, k) = C(n−1, k−1) + C(n−1, k) builds the table without division (Module 49 computes it modulo a prime).
Pigeonhole: placing n + 1 items into n boxes forces a box with two items — e.g. among any 13 people, two share a birth month.
Inclusion–exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|. Numbers in 1..100 divisible by 2 or 3: 50 + 33 − 16 = 67.
3.8 Probability basics
Expected value, independent events, linearity of expectation, randomization, and expected complexity of randomized algorithms.
Linearity of expectation holds even for dependent variables: the expected number of fixed points of a random permutation of n items is n · (1/n) = 1, whatever n is. Module 51 uses the same idea to analyse randomized quicksort.
3.9 Bitwise operations
&, |, ^, ~, <<, >>; set/clear/toggle/test a bit; masks; parity; power-of-two checks; subset masks; bit counting. Explain integer-width and signed-shift hazards.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Hazards: shifting by at least the bit width is undefined; left-shifting a negative signed value is undefined before C++20; right-shifting a negative value was implementation-defined before C++20. Use unsigned types (or 1LL / 1ULL) for masks.
#include <bits/stdc++.h>
using namespace std;
int main() {
unsigned x = 0b10110; // 22
cout << "x = " << bitset<8>(x) << '\n';
cout << "set bit 0 = " << bitset<8>(x | 1u << 0) << '\n';
cout << "clear bit 2 = " << bitset<8>(x & ~(1u << 2)) << '\n';
cout << "toggle bit 4 = " << bitset<8>(x ^ 1u << 4) << '\n';
cout << "test bit 1 = " << ((x >> 1) & 1u) << '\n';
cout << "lowest set = " << bitset<8>(x & -x) << '\n';
cout << "popcount = " << __builtin_popcount(x) << '\n';
for (unsigned v : {1u, 6u, 64u, 0u})
cout << v << " is power of two: " << boolalpha << (v != 0 && (v & (v - 1)) == 0) << '\n';
cout << "subsets of {a,b,c}:";
for (int mask = 0; mask < 1 << 3; ++mask) {
cout << " {";
for (int i = 0; i < 3; ++i) if (mask >> i & 1) cout << char('a' + i);
cout << '}';
}
cout << "\n1LL << 40 = " << (1LL << 40) << " (1 << 40 on a 32-bit int would be undefined)\n";
}x = 00010110
set bit 0 = 00010111
clear bit 2 = 00010010
toggle bit 4 = 00000110
test bit 1 = 1
lowest set = 00000010
popcount = 3
1 is power of two: true
6 is power of two: false
64 is power of two: true
0 is power of two: false
subsets of {a,b,c}: {} {a} {b} {ab} {c} {ac} {bc} {abc}
1LL << 40 = 1099511627776 (1 << 40 on a 32-bit int would be undefined)Practice
Easy: count numbers in 1..1000 divisible by 3, 5 or 7 with inclusion–exclusion.
Medium: compute aᵇ mod m for b up to 10¹⁸ and explain why the loop runs about 60 times.
Hard: using the sieve, list all primes in [10¹², 10¹² + 10⁶] (segmented sieve).
Quiz
? Why compute `lcm` as `a / gcd(a,b) * b`?
+ Dividing first keeps the intermediate value small and avoids overflow. :: The run computed lcm of 4·10⁹ and 6·10⁹ as 1.2·10¹⁰, while a·b would overflow long long.
- It is faster than multiplying first. :: Speed is not the point.
- gcd must be computed after multiplication. :: Order is the point, but for overflow.
- It handles negative numbers. :: Not the reason.
? What does `-7 % 5` evaluate to in C++?
- 3 :: That is the mathematical (normalized) remainder.
+ -2 :: C++ truncates toward zero, so the remainder takes the dividend's sign.
- 2 :: No.
- Undefined :: It is defined since C++11.
? Which checks correctly test that a positive unsigned `v` is a power of two? (select all that apply)
+ `(v & (v - 1)) == 0` :: Clears the lowest set bit; zero means only one bit was set.
+ `__builtin_popcount(v) == 1` :: Exactly one bit set.
- `v % 2 == 0` :: True for 6, which is not a power of two.
- `(v | (v - 1)) == 0` :: Never true for v ≥ 1.Related topics
Module 27 (bit manipulation), Module 48 (number theory), Module 49 (combinatorics), Module 51 (probability and randomization).