Project Euler Problem 1: Multiples of 3 and 5 Solution

P

Problem Statement

(see projecteuler.net/problem=1)

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 1000.

Solutions

#include <iostream>
// triangular number:∑x=1+2+..+x=x∗(x+1)/2
unsigned long long sum(unsigned long long x)
{
return x * (x + 1) / 2;
}
int main()
{
unsigned int tests;
std::cin >> tests;
while (tests––)
{
unsigned long long last;
std::cin >> last;
// not including that number
last––;
// find sum of all numbers divisible by 3 or 5
auto sumThree = 3 * sum(last / 3);
auto sumFive = 5 * sum(last / 5);
// however, those numbers divisible by 3 AND 5 will be counted twice
auto sumFifteen = 15 * sum(last / 15);
std::cout << (sumThree + sumFive – sumFifteen) << std::endl;
}
return 0;
}
public final class p001 implements EulerSolution {
public static void main(String[] args) {
System.out.println(new p001().run());
}
/*
* Computers are fast, so we can implement this solution directly without any clever math.
* A conservative upper bound for the sum is 1000 * 1000, which fits in a Java int type.
*/
public String run() {
int sum = 0;
for (int i = 0; i < 1000; i++) {
if (i % 3 == 0 || i % 5 == 0)
sum += i;
}
return Integer.toString(sum);
// 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 1000.
var total = 0;
for (var i = 1; i < 1000; i++) {
if (i % 3 === 0 || i % 5 === 0) {
total += i;
}
}
console.log(total)

HackerRank

see https://www.hackerrank.com/contests/projecteuler/challenges/euler001

My code solves 5 out of 5 test cases (score: 100%)

Difficulty

5% Project Euler ranks this problem at 5% (out of 100%).

Hackerrank describes this problem as easy.

Note:
Hackerrank has strict execution time limits (typically 2 seconds for C++ code) and often a much wider input range than the original problem.
In my opinion, Hackerrank’s modified problems are usually a lot harder to solve. As a rule thumb: brute-force is rarely an option.

References

projecteuler.net/thread=1 – the best forum on the subject (note: you have to submit the correct solution first)

Code in various languages:

About the author

1 comment

By admin

Mailchaimp

About Me

I like to Code and Love to share the codes.