# CPP Program for Multiples of 3 and 5 with Source Code

## Problem:

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

## Algorithm:

• We are supposed to find all multiples of 3 or 5 below the input number, therefore we decrement it by one.
• In general, the sum of all numbers between 1 and `x` is `sum_{1..x}i=x * (x+1)/2` (see https://en.wikipedia.org/wiki/Triangular_number )
• There are `floor{x/3}` numbers between 1 and x which are divisible by 3 (assuming `floor{x/3}` is an integer division). e.g. the range `1..10` contains `floor{10/3}=3` such numbers (it’s 3, 6 and 9). Their sum is `3+6+9=18`.
• This can be written as `3/3 * (3+6+9)` which is the same as `3 * (3/3+6/3+9/3)=3 * (1+2+3)`.
• Those brackets represent `sum_{1..3}i = sum_{1..10/3}i` (or short: `sum{10/3}`) and thus our overall formula for the sum of all multiples of 3 becomes `3 * sum{x/3}`.
• The same formula can be used for 5: The sum of all numbers divisible by 5 is `5 * sum{x/5}`
• However, there are numbers divisible by 3 and 5, which means they are part of both sums.
• We must not count them twice, that’s why we (in addition to the aforementioned sums) compute the sum of all numbers divisible by 3*5=15 to correct for this error.
• In the end we print ”sumThree + sumFive – sumFifteen”

## Alternative:

• Looping through all numbers from 1 and 1000 and checking each of those numbers whether they are divisible by 3 or 5 easily solves the problem, too, and produces the result pretty much instantly.
• Even more, the code will be probably a bit shorter.
• However, Hackerrank’s input numbers are too large for that simple approach (up to `10^9` with `10^5` test cases) and will lead to timeouts.

## Program:

```.wp-block-code {
border: 0;
}

.wp-block-code > span {
display: block;
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
```#include <iostream>

// triangular number: `sum{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;
}
```Code language: C++ (cpp)```