15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Topic 3 of 12 in the free DSA Basics course · 6 lessons
Build a small set of integer utilities for positive or nonnegative inputs:
Each utility is small enough to test with known inputs. Trace changing variables and state the rule that keeps each algorithm correct.
None.
You need comfort with basic multiplication, division, remainders, and writing simple loops and conditionals. The sequence starts with divisors and builds toward algorithms that use remainders, binary digits, and repeated decomposition.
Use the pair 84 and 30 to connect factorization, GCD, and LCM.
First factor both numbers:
84 = 2^2 × 3 × 730 = 2 × 3 × 5To compute the GCD with the Euclidean algorithm, record the changing pair:
(a, b) = (84, 30), and 84 mod 30 = 24(a, b) = (30, 24), and 30 mod 24 = 6(a, b) = (24, 6), and 24 mod 6 = 0The last nonzero remainder is 6, so gcd(84, 30) = 6.
The factorizations give the same result: keep the prime powers shared by both numbers at their smaller exponents:
gcd = 2 × 3 = 6For the LCM, keep every prime power needed by either number at its larger exponent:
lcm = 2^2 × 3 × 5 × 7 = 420Check the result with:
gcd(84, 30) × lcm(84, 30) = 6 × 420 = 84 × 30Trace the remainder states and compare the result with the prime-factor view to verify the code.
Divisibility Logic applies decomposition and remainder reasoning to checks based on final decimal digits and digit sums.
Prime Numbers & Factorization establishes divisors, primes, and prime decompositions. These ideas explain shared factors and combined factors.
GCD and LCM uses division with remainder to find the greatest shared divisor efficiently, then uses that result to compute the least common multiple.
Modular Arithmetic extends remainder thinking. Work with numbers that have the same remainder under a chosen modulus.
Binary Representation & Bit Tricks moves from decimal place values to powers of two. Remainders modulo powers of two and binary positions make bit operations easier to interpret.
Fast Exponentiation uses the binary representation of an exponent. Each step consumes one binary digit by halving the exponent and squaring the base.
The sequence begins with the structure of integers. Explaining why 84 and 30 share a factor of 6 requires divisors and prime factors. Trial division introduces a runtime pattern: when searching for a factor, test candidate divisors through the square root.
GCD uses the Euclidean algorithm. Replacing (a, b) with (b, a mod b) preserves the set of common divisors. That stable rule explains why the final nonzero remainder is the GCD. The number of steps depends on repeated remainder operations, not on scanning every integer up to the inputs.
Modular Arithmetic builds directly on a mod b. Values are equivalent when they leave the same remainder. Normalize negative results when needed: for modulus m > 0, use ((x % m) + m) % m to obtain a residue from 0 through m - 1.
Binary Representation & Bit Tricks changes the base used to describe a number. For example, 10110₂ means:
1 × 2^4 + 0 × 2^3 + 1 × 2^2 + 1 × 2^1 + 0 × 2^0Each displayed bit contributes a value determined by its position and its power of two. Shifts, masks, and power-of-two tests use those positions.
Fast Exponentiation uses binary structure. Repeatedly square the base and halve the exponent. Halving means the number of loop iterations grows with the number of bits in the exponent.
Divisibility Logic returns to remainders in decimal form. A digit scan can update a remainder with remainder = (remainder × 10 + digit) mod m, so you can test divisibility without first constructing a potentially large full number.
Finish with Divisibility Logic. Check numbers using remainder tests, digit sums for 3 and 9, final digits for 2, 5, and 10, and the final two digits for 4. Implement a digit scan and compare its result with direct remainder computation on small inputs.
Start with Prime Numbers & Factorization. Test values such as 1, 2, 49, and 84. Verify every factorization by multiplying its prime powers back together.
Continue with GCD and LCM. Trace gcd(84, 30) by hand, then test that positive inputs satisfy gcd(a, b) × lcm(a, b) = a × b.
Practice Modular Arithmetic with addition, subtraction, and multiplication under a small modulus. Include a negative value and confirm that your normalized residue is in the required range.
In Binary Representation & Bit Tricks, convert several small decimal numbers to binary and back. Write bit traces with a fixed width so leading positions are visible.
Use Fast Exponentiation to compute a small power both by repeated multiplication and repeated squaring. Then add a modulus and reduce after multiplication.