self.debug 01 : Competitive programming and Math

Bug

Note: I wrote this last year, before I began reviewing my computer science foundations

I found out that I suck in coding solutions for algorithmic problems . I suck so  hard that I can't get the highest score  for the 1st Project Euler problem  . Don't get me wrong, I was able to code a working solution but I wasn't able to use Math ninjutsu  and make it run as fast as O(1).

The problem is described below:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below N.

My initial solution was to loop through all the numbers less than N ( brute force and the slowest design ever), check if it is a multiple of 3 or 5, then add it to the sum. This would work but the running time is O(n). Hackerrank would only give you 40 out of 100 points.

It took me a half a day (alt+tab between work and the problem ) to come up with a solution. I remembered that this is related to a BASIC arithmetic series whose equation is described below:

f(n) =  n( a1 + an / 2)

fair enough I coded the function and got the sum for the multiples of 3 and 5. The problem is, the two series converge at some point. i.e 15, 30 .. numbers divisible by 15.  I deducted the sum for 15 and tadaaa I got O(1). Actually it's another half day trying to figure out how to make BigDecimal faster!!! So all in all I spent almost day at work (perhaps 3- 4 hours to be exact minus the work stuff) to solve a single Project Euler problem!

*gasp*

!? *gasp*

Steps to replicate

Solve a project Euler challenge in  hackerrank Lie down, roll,  cry...

Root Cause

TL;DR

Yep! I'm pretty sure it's another conscious incompetence moment

  I had to debug myself and listed the following reasons:

The illusion of competence

After reading  "A mind for numbers" I realized that, I was under this illusion that I'm good at Math because I was fast in understanding the concepts. I should have known early on that being good at something  doesn't necessarily require being a fast learner, but what's important is that you have been able to to chunk the concepts and you have them cemented into your long term memory. If I have known memory chucking techniques before, perhaps solving the hacker rank problem had been a different experience

I admit that I was hell of a lazy student. Instead of taking down notes , I would doodle on my notebook , and instead of spaced repetition and practice I would often just study before the exams.

I also never got the chance to use Math in my development career. Don't get me wrong, Math has always been there, but they had been abstracted by some library or API.

So yeah I think that's about it, minus the ego and pride stuff. 

Solution

What I plan to do is to review everything from scratch, This time using proper learning techniques etc. This would be beneficial to my career and to also to my future  kids :P 

Arithmetic sequence and series song

Play this on the  background then sing the lyrics :
https://www.youtube.com/watch?v=SswjdoAAJb8


An arithmetic sequence has a constant difference
The sum of athe sequence is series

In order to get the nth term
you must know the first term
then you add the constant difference

Chorus
That's multiplied, that's multiplied
to n minus one
That is how you get the nth Term

An arithmetic sequence has a constant difference
The sum of the sequence is series

In order to get the sum of the sequence
you must know the first term
then you add the nth term

Chorus
That's multiplied , that's multiplied
by n over two
That is how you get the sum of terms

Useful links:
https://www.khanacademy.org/math/precalculus/seq_induction/seq_and_series/v/explicit-and-recursive-definitions-of-sequences


Idea :
Math formula karaoke
Math funny visual aids