Problem statement: How many trailing zeros in 103!
Method:
Recall n! = n(n-1) … 1
Zeros can be added by n * (10 * x) or 2n * 5x
floor(103/5) = 20, floor(103/5^2) = 4 Total = 24
If 5^3 < n, floor (n/5^3) would be added also
Comb 2.
Problem statement: GIven int n, find the number of divisors of n.
Method:
Prime factorization: n = a^x * b^y * c^z
Use combinatorics: number of ways to choose a^x * num ways to choose b^y * num ways to choose c^z = xyz
Therefore, number of divisors = xyz
Algorithm:
1. Using sieve of Eratosthenes
2. Combinatorial method
O(log n) prime factorization algorithm with O(n) for prime numbers
Use hashmap to store prime counts, multiply all counters
Optimizations: sieve, square root
Total complexity O(log n) or worst case O(n) compared to O(n) sieve for single test cases
Comb 1.
Topic: Combinatorics
Problem statement: How many odd numbers with 3rd digit 5 between 20000 and 69999?
Method:
How many ways to choose each digit?
20500 21500 … 69500
How many ways to choose the last digit?
00 … 99
50 * 50 = 2500
LT 3.
Topic: Proportionality I
Problem statement: It is 4 o’clock now. How many minutes will pass until the hands of the clock are coincident?
Method:
Notice an hour is directly proportional to minutes by 60 E.g when the minute hand moves 20 mins, the hour hand moves 20/60 = ⅓ hours
Let x = minutes passed. The hour hand has gone x/60 of the way from 4pm to 5pm
4 hours can also represent 20 mins for the minute hand. There are 5 minutes between the hourly intervals of 4 and 5.
Therefore, x = 20 + 5(x/60)
x = 240/11 mins
Key observations:
Direct and inverse proportions are constant (x/y, xy) given different values of xor x, y
Problems can be split into 2 proportions (LT 2), then combined like (LT 1)
Use algebra with proportions to find the solution. How can proportions be combined or represented in a common form? Time difference = current time + new time (LT 3)
LT 2.
Topic: Proportionality I
Problem statement: It takes 3 days for 4 people to paint 5 houses. How long will it take
2 people to paint 6 houses?
Method:
Notice days and people are directly proportional to houses and inversely proportional to each other
houses/(people)(days) = 5/12 (from problem statement 1)
Days = 12/5 * houses/people (algebra)
Days = 36/5
LT 1.
Topic: Proportionality I
Problem statement:
Proof (*):
Let x/y = a/b, where y = w/yz (from other question)
x = y * (a/b)
Method:
Notice x is directly proportional to y, x -> x/y and x/z are constant, xw is constant as it is inversely proportional
A perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, 6 has divisors 1, 2 and 3 (excluding itself), and 1 + 2 + 3 = 6, so 6 is a perfect number.
The Euclid–Euler theorem is a theorem in number theory that relates perfect numbers to Mersenne primes. It states that an even number is perfect if and only if it has the form 2^(p−1) * (2p − 1), where 2p − 1 is a prime number. The theorem is named after mathematicians Euclid and Leonhard Euler, who respectively proved the "if" and "only if" aspects of the theorem.
Sufficiency Proof:
2^p - 1 is prime
σ(2^(p - 1)(2^p - 1)) = σ(2^(p - 1))σ(2^p - 1)
The divisors of 2^(p - 1) are 1, 2, 4, 8, …, 2^(p-1) form a geometric series that sum to 2^p - 1.
Since 2^p - 1 is prime, it has 2 divisors: 2^p - 1, 1. The sum of the divisors is 2^p
Suppose an even perfect number is given, and partially factor it as 2^(k)x = σ(2^(k)x) = (2^(k + 1) - 1)σ(x) *
The odd factor on the right, 2^(k + 1) - 1 is at least 3 and must divide x, the only odd factor on the left side -> y = x / 2(2^(k + 1) - 1) is a proper divisor of x
Dividing both sides of (*) by common factor 2^(k + 1) - 1 and taking into account known divisors x, y of x -> 2^(k + 1)y = σ(x) = x + y + … = 2^(k + 1)y + …
Therefore, there cannot be other divisors, y = 1, and x must be prime of the form 2^(k + 1) - 1.
Alg 1.
Topic: Logarithms & exponentiation
Problem statement: Given a != c, a^x = c^q, a^z = c^y. Prove that xy = qz.
Method:
Try multiplying the expressions to get a^x*c^q or …
Dead end -> return
Cancel out a to get c as the same base on both sides
How to cancel out a? a = (a^x)^(1/x) = c^(q/x) = (a^z)^(1/z) = c^(y/z)
Now we have c^(q/x) = c^(y/z) -> q/x = y/z -> xy = qz
Key takeaway:
Try multiple problem solving tactics. Think creatively.
Develop the thoughts through notation.
Think backwards & forwards (to prove that xy = qz, we need to extract the exponents. To extract the exponents, the base must be equal. Therefore, we have to construct either a^something = a^something else or c … etc.)
If there’s an equals sign, try to find equivalences