Competitive Programming and Number Theory are quite interesting things to do in spare time. And a chaotic mind such as my own always needs a break from the mundane things of reality and life every once in a while. However, don’t be fooled, competitive programming can get boring as hell sometimes.
Back in college, when I was first introduced to competitive programming, we were a select few students who were fascinated and even fewer of us, myself excluding unfortunately, were in it for the long run. Its quite helpful for placements, helps you brush up a few concepts on mathematics, and who knows, might be even useful to you in your job as well.
Since I’m restarting, I thought of best trying my hand at Project Euler first. The problems are designed to teach a person to look for efficient solutions that can solve it under a minute, and you might learn something new from each problem you approach as you level up. Sounds like a nice restart.
Here are all the problems I have solved (again) so far, along with my experience solving them:
- Multiples of 3 and 5 - Dude, come on.
- Even Fibonacci Numbers - Took me a minute to write the simplest solution, took me another 2 minutes to figure out the solution listed in the problem’s editorial.
- Largest Prime Number - Easy peasy, prime factor of a composite number n cannot exceed sqrt(n).
- Largest palindrome product - Simple solution worked for me.
- Smallest multiple - Dude, come on.
- Sum square difference - Dude, come on.
- 10001st Prime - Dude, come on.
- Largest product in a series - Easy, but writing code took me a bit longer. Sliding window jutsu.
- Special Pythagorean triplet - Brute-force the damn thing and it will run under a minute.
- Summation of primes - Go to Cyrene. There’s a guy who solved this.
- Largest product in a grid - Easy because brute-force all over again. Since, its just 20x20, we’ll be fine. Writing code for traversal of rows, columns and diagonals sucks though.
- Triangular Number - Iterate triangular numbers in a loop, check number of divisors for each, easy peasy.
- Large Sum - :cough: :cough: Python.
- Longest Collatz Sequence - Just go for the easy solution.
- Lattice Paths - Difficult for me. My combinatorics is a bit rusty now. Although, I was able to reach to the ultimate solution, I did have a bit of help on this one. I wrote a path-counting solution by imagining the whole thing as a graph of 21x21 vertices, and recorded answers for smaller inputs - 2x2, 3x3, 4x4, 5x5 and so on. And then, I used OEIS.
- Power Digit Sum - Dude, come on.
- Number Letter Counts - Use inflect, its less hassle if you are lazy like me.
- Maximum Path Sum I - Dynamic programming, solve the problem bottom up. The total complexity should be O(n), where n is the number of nodes.
- Counting Sundays - Python datetime, need I say more?
- Factorial Digit Sum - Use python, it can easily compute large factorials for such problems without you sweating.
- Amicable Numbers - We already know how to get the proper divisors of a number. Just sum them up, write sum comparison code and do all this in a loop.
- Names Scores - I’m keeping the text file. Seriously, I’ve been looking for a names db to cook up random excuses in my personal e-mail. Later.