Programming vs. Programming with Math

There are plenty of online resources for learning programming and getting into software development industry. Since they are easy to find and most of their titles are indicating that you can be a senior developer within a month or several weeks or even hours, a lot of new programmers are growing up every year. And there is only one way to distinguish good programmers from bad programmers. Respectively they are programmers who love math and programmers who think math is useless.

We at high school :)

Yes, kids, we have left our most important skills in high school.

Since there are still people who believes programming has nothing to do with math, I am going to bring a very simple example here.

A while ago I was practicing some problems from HackerRank I entered to the competition called Project Euler (you can see the list of problems here).

If you try to solve the problems from archive website you will find them easy and you will most likely succeed to solve them. However, if you enter to the competition in HackerRank, since there are plenty of test cases and time, memory limit you will have to rethink your solution. Still don’t believe me?

Let’s look at the first problem of Project Euler. It is called Multiples of 3 and 5.

Problem asks us to find find the sum of all the multiples of 3 or 5 below N. Here N is any counting number between 1 and one billion, inclusive.

And here is some example input, output and explanation.

First solution comes to mind is brute force; we simply loop through each element starting from 3 till N (exclusive) and we add it to some variable if it is divisible by 3 or 5.

#include <iostream>

using namespace std;

int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        int n;
        cin >> n;
  
        int sum = 0;
        for (int i = 3; i < n; i++) {
          if (i % 3 == 0 || i % 5 == 0)
            sum += i;
        }
      
        cout << sum << endl;
    }
    return 0;
}

This is an O(n) solution and it works, yeah, and this is totally correct solution. Unfortunately above statements are true until you submit this code… Try to submit it on HackerRank and you will see some test cases failing with this error: Terminated due to timeout.

Well, performance issues... It’s not uncommon :)

So, this solution is not fast enough. What do we do to be faster? Nothing. Math comes to help!

Let’s rethink the solution; Remember the sequences and series from math? Well, if not then have a look at this website to refresh your knowledge. What we need to look at is the sum of sequence formula

Sum of the sequence

From here we notice that if we need to find sum of numbers till N (inclusive) we don’t need a for loop. We can do it in constant time, thanks to the formula.

So, let’s apply this formula to our case. We first need to find sum of all numbers divisible by 3, then sum of all numbers divisible by 5, but then we need to subtract all numbers divisible by 3 and 5 (divisible by 15) from the result. See the stackexchange answer for further clarification.

Let’s say we need to find sum of all numbers divisible by 3 till 100 (exclusive). Here is how we do this:

Simple sum example

We are going to do the same thing for 5 and 15. Then after adding sum of all numbers divisible by 3 and sum of all numbers divisible by 5, we will subtract sum of all numbers divisible by 15 from them. Something like this:

int sumDivisibleBy3 = 3 * (( n / 3 * (n / 3 + 1) ) / 2);
int sumDivisibleBy5 = 5* (( n / 5 * (n / 5 + 1) ) / 2);
int sumDivisibleBy15 = 15 * (( n / 15 * (n / 15 + 1) ) / 2;
int finalSum = sumDivisibleBy3 + sumDivisibleBy5 - sumDivisibleBy15;

That’s a simple way to put, and here is the actual solution code.

#include <iostream>

using namespace std;

int main(){
    long t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        long n;
        cin >> n;
        n = n - 1;

        long long sum = 0;
        
        long three = n / 3, 
             five = n / 5, 
             fifteen = n / 15;
        
        sum += ((3 * three * (three + 1)) / 2);
        sum += ((5 * five * (five + 1)) / 2);
        sum -= ((15 * fifteen * (fifteen + 1)) / 2);

        cout << sum << endl;
    }
    return 0;
}

Go ahead, try to submit this solution, you will see that it passes all test cases without breaking the time limit. And we use long values because int values cannot store values greater than 2147483647 and there are really high numbers in the test cases. If you find anything to fix here, please let me know.

Conclusion

To sum up, I recommend anyone to look at the Project Euler problems in HackerRank, it will really help you to think about performance of your program. And in real life you do have to think about performance.

I am not a math genius, I was one of those who wrote a for loop and watch it to fail. So, I am glad I learned.

Thanks for reading! And if anyone come up with JavaScript solution, please, share in the comments. I could not play with numbers in JavaScript and I had to write it in other language.

Update:

Just found a way to do it with JavaScript using BigInt since it can hold values up to 2 to the power 53. You can read more about BigInt at MDN.

And here is the solution. Since the BigInt syntax is new, code editors may not recognize them.

function main() {
    var t = BigInt(readLine());
    for (var a0 = 0; a0 < t; a0++) {
        var n = BigInt(readLine());
        n = n - 1n;
        var sum = BigInt(0);
        var temp1 = n / 3n,
            temp2 = n / 5n,
            temp3 = n / 15n;

        sum += (3n * temp1 * (temp1 + 1n) / 2n);
        sum += (5n * temp2 * (temp2 + 1n) / 2n);
        sum -= (15n * temp3 * (temp3 + 1n) / 2n);
        
        // this is to remove 'n' from the output
        console.log(sum.toString().substring(0, sum.toString().length));
    }
}