20 interleaved questions drawn from every lesson in this phase. Interleaving mixes topics on purpose - that difficulty is what builds durable, transferable understanding. Aim for 70%+ before advancing; below that, revisit the flagged lessons.
Q1 MediumWhy does \(\gcd(a,b)=\gcd(b,a\bmod b)\) hold?
Because \(a\bmod b\) is always smaller than \(b\)
Because the pairs \((a,b)\) and \((b,a\bmod b)\) have exactly the same set of common divisors
Because gcd is commutative
Because \(b\mid a\) whenever \(a\gt b\)
Q2 MediumWhy may the sieve start crossing out multiples of \(p\) at \(p^2\)?
Because \(p^2\) is the first composite
Because any multiple \(kp\) with \(k\lt p\) has a prime factor smaller than \(p\) and was already crossed out
Because \(p^2\gt n\) usually
To save memory
Q3 EasyWhen does \(a\) have an inverse modulo \(n\)?
Whenever \(a\lt n\)
Whenever \(n\) is prime
Exactly when \(\gcd(a,n)=1\)
Whenever \(a\) is prime
Q4 MediumWhy is float(2**53) + 1 == float(2**53) true?
A bug in Python
Doubles have 53 bits of significand, so the gap between representable numbers at \(2^{53}\) is 2
Because \(2^{53}\) is odd
Because addition is not associative
Q5 MediumHow many ways are there to choose 3 scoops from 5 flavours, repetition allowed, order irrelevant?
\(5^3=125\)
\(\binom 53=10\)
\(\binom{5+3-1}{3}=35\)
\(5\cdot4\cdot3=60\)
Q6 HardThe characteristic equation of \(a_n=4a_{n-1}-4a_{n-2}\) has a repeated root 2. The general solution is:
\(\alpha 2^n\)
\(\alpha2^n+\beta2^n\)
\(\alpha2^n+\beta n2^n\)
\(\alpha2^n+\beta(-2)^n\)
Q7 HardDP requires overlapping subproblems AND optimal substructure. What goes wrong if only overlap holds?
Nothing
The cache gives wrong answers, because an optimal whole may not be built from optimal parts
It becomes too slow
Memory blows up
Q8 Mediumx & (x-1) computes:
x with the lowest set bit cleared
The lowest set bit
The popcount
x divided by 2
Q9 MediumWhy does Dijkstra fail with negative edge weights?
The heap breaks
A vertex settled as ‘nearest’ may later be improved through a negative edge, violating the exchange argument
It becomes too slow
It only fails on directed graphs
Q10 MediumBranch-and-bound is guaranteed to find the optimum only if the bound is:
Tight
Admissible (never worse than the best possible completion)
Fast to compute
Monotone
Q11 MediumWhy does \(\prod_{k\ge1}(1-x^k)^{-1}\) generate \(p(n)\)?
It is the Taylor series of an exponential
Each factor \(1/(1-x^k)=1+x^k+x^{2k}+\cdots\) records how many copies of the part \(k\) are used, and the choices are independent
Because \(p(n)\) is multiplicative
By the pentagonal number theorem
Q12 EasyThe continued-fraction expansion of a rational \(p/q\) is:
Infinite
Exactly the sequence of quotients produced by the Euclidean algorithm on \((p,q)\)
Always periodic
Only defined for \(p\lt q\)
Q13 MediumWhy does \(\begin{pmatrix}1&1\\1&0\end{pmatrix}^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}\) let you compute \(F_n\) fast?
Because matrices are faster than integers
Because a matrix power can be computed by repeated squaring in \(O(\log n)\) multiplications
Because the matrix is symmetric
Because the determinant is \(-1\)
Q14 MediumYour algorithm is \(\Theta(n^2)\) and \(n=10^5\). In pure Python, roughly how long?
Under a second
About a minute
About 10 days - \(10^{10}\) ops at \(\sim10^7\) ops/s
It depends only on the constant
Q15 MediumExtended Euclid on \((a,b)\) with \(\gcd(a,b)=1\) returns \(x\) such that:
\(x=a^{-1}\bmod b\)
\(x=b^{-1}\bmod a\)
\(x=\operatorname{lcm}(a,b)\)
\(x\) is always positive
Q16 MediumYou must factor \(10^6\) different integers, each below \(10^7\). Best approach?
Trial division per query
Pollard rho per query
Build a smallest-prime-factor sieve once, then divide down per query
Miller–Rabin per query
Q17 MediumHow many modular multiplications does square-and-multiply need for \(a^{10^{18}}\bmod n\)?
About \(10^{18}\)
About 120 - two per bit of the exponent
About \(\sqrt{10^{18}}=10^9\)
It depends on \(a\)
Q18 MediumTo evaluate \(\sqrt{x+1}-\sqrt{x}\) accurately at \(x=10^{16}\) you should:
Use higher precision floats
Rewrite as \(1/(\sqrt{x+1}+\sqrt{x})\)
Round the result to 3 decimals
Use math.fsum
Q19 MediumWhy can’t you compute \(\binom{n}{k}\bmod p\) by dividing the reduced factorials?
Because factorials are too big
Because division is not an operation in \(\Z/p\Z\); you must multiply by modular inverses
Because \(p\) might not be prime
Because Pascal’s rule forbids it
Q20 MediumThe generating function \(F(x)=x/(1-x-x^2)\) encodes Fibonacci because:
It converges for all x
Multiplying the recurrence by \(x^n\) and summing produces \(F(x)-x=(x+x^2)F(x)\)
Its derivative is \(F_n\)
It equals \(\varphi^n\)