Sum of multiples of 3 and 5 (Project Euler Problem 1)

Reading time: 30 minutes | Coding time: 5 minutes

The problem at hand is to find the sum of all numbers less than a given number N which are divisible by 3 and/ or 5. We will explore this problem and show multiple solutions with a constant time O(1) solution as well.

In this problem, you get the idea of how to get the sum of consecutive integers in constant time without actually adding them. With the idea of the problem, you can solve the Problem 1 of Project Euler as well.

Example:

If we consider N=20, then the numbers that are divisible by 3 and/ or 5 are:

3, 5, 6, 9, 10, 12, 15, 18, 20

The sum of the numbers is 98. Hence, 98 is our answer for N = 20.

Basic idea to solve this problem efficiently is:

Sum of integers from 1 to N = N * (N-1) / 2

Simple solution O(N)

The simple solution is to traverse through all elements from 1 to N and check for each element if it is divisible by 3 or 5. If it is divisible, we shall add it to a common variable.

Pseudocode:

sum = 0;
for i from 1 to N
    if i % 3 == 0 OR i % 5 == 0
        sum += i;

If we assume that modulas operation takes constant time, the overall complexity of the algorithm is O(N).

In reality, operations like multiplication and modulas takes O(log N) time and hence, the time complexity of this approach will be O(N log N).

Implementation:

class opengenus 
{
    static int find_sum(int N)
    {
        int sum = 0;
        for(int i = 1; i < N; i++)
            if(i%3 == 0 || i%5 == 0)
                sum += i;
        return sum;                
    }

	public static void main (String[] args) 
	{
		int N = 10000;
		int sum = find_sum(N);
		System.out.println(sum);
	}
}

Output:

23331668

This approach works fast for smaller numbers and even, we go to higher numbers like 10^9, this becomes slow. To tackle this, we will build our constant time algorithm.

Efficient approach

We will solve this problem in constant time.

Let us solve the limited version of the problem where we need to find the sum of numbers that are divisible by 3. For this, we can take the previous approach of checking each number of take advantage of a fundamental mathematical property.

The property is:

Sum of numbers from 1 to N is N * (N-1) / 2.

This means the sum of numbers from 1 to 1000 is simply 1000 * 999/2 = 499500.

You need to understand how this will help us.

Consider the first 5 multiples of 3 that is:

3, 6, 9, 12, 15 which is same as 3 multiplied by the first 5 integers (1, 2, 3, 4, 5).

Sum of first 5 multiples of 3=
= 3 + 6 + 9 + 12 + 15
= 3 * (1 + 2 + 3 + 4 + 5)
= 3 * (sum of first 5 integers)

We know the sum of first 5 integers as 5 * 4/2 = 10. So, the sum of first 5 multiples of 3 is 3 * 10 that is 30.

To find the sum of numbers < N which are multiples of 3, we need to find the upper limit of multiples of 3. Let us denote the upper limit as M.

It is such that:

M * 3 <= N and (M+1) * 3 > N

This can be easily figured out by dividing N by 3 and taking the floor of the number. Alternative approach is to find the modulus of N by 3 and subtract it from N which we can then divide by 3.

Upper limit of multiple of 3 series = M

M = floor (N / 3) 
or
M = (N - N%3) / 3 

Hence, for any given N, to find the sum of numbers divisible by 3 and less than N:

• We need to find M
• Sum = 3 * M * (M-1) / 2

Similarly, for 5:

M = floor (N / 5) 
or
M = (N - N % 5) / 5 
Sum = 5 * M * (M-1) / 2

We can find the sum of multiples of 3 and 5 separately. At this point, if we add both, we get a number which has the multiples of 15 (3 * 5) added twice. To get our ultimate answer, we need to subtract multiples of 15 from the sum.

This is simple as we can use our insights to get the sum of multiples of 15.

Hence, the final solution is:

Sum of numbers less than N which are multiples of 3 
= Sum of multiples of 3 + Sum of multiples of 5 - Sum of multiples of 15

Find the sum of multiples of 3 or any given numbers takes constant time O(1) if you consider basic operations like multiplication takes O(1) time.

Pseudocode:

find_sum(N, multiple)
{
    M = (N - N % multiple) / multiple;
    sum = multiple * M * (M-1) / 2;
    return sum;
}

sum = find_sum(N, 3) + find_sum(N, 5) - find_sum(N, 15)

Implementation:

class opengenus 
{
    static int find_sum(int N, int multiple)
    {
        int M = (int)((N - N % multiple) / multiple);
        int sum = (int)(multiple * M * (M-1) / 2);
        return sum;
    }

	public static void main (String[] args) 
	{
		int N = 10000;
		int sum = find_sum(N, 3) + find_sum(N, 5) - find_sum(N, 15);
		System.out.println(sum);
	}
}

Output:

23331659