Five to Three - Fifteen

Project Euler #1: Multiples of 3 and 5

Читать на Русском

Problem Statement on  HackerRank ProjectEuler+. This problem is a programming version of problem #1 from ProjectEuler.

Given a positive integer n. Find the sum of all positive integers below n that are multiples of 3 or 5.

Input format

First line contains t (1 ≤ t ≤ 10000) that denotes the number of test cases. Each of the following t lines contains single integer n (1 ≤ n ≤ 10000).

Output format

For every n print the sum of all positive integers below n that are multiples of 3 or 5.

Status: Accepted

Before reading the editorial I recommend you to solve the problem by yourself.

Analytical solution

Lets sum all integers below n that are multiples of 3, after it lets add to them all integers below n that are multiples of 5. From this sum we should subtract all integers below n that are multiples of 15 because we have already counted them twice.

Solution

Note that the number of multiples of 3 below n, is equal to the partial quotients by dividing n-1 by 3. For calculating the sum we can use the formula of the sum of first k numbers in an arithmetic progression, where k is (n-1)/3.
The following code will count the sum for multiples of three:

int k = (n-1)/3;
sum = ((3 + k*3)*k)/2;

or

int k = (n-1)/3;
sum = 3*(k+1)*k/2;

Just add a simillar code for 5 и 15. Also don`t forget a about possible integer overflow. The final code:

int t, n, c;
cin >> t;
long long sum;
for (int i = 0; i < t; ++i) {
  cin >> n; 
  sum = 0;
  n--;
  c = n/3;
  sum += 3ll*(c+1)*c/2;
  c = n/5;
  sum += 5ll*(c+1)*c/2;
  c = n/15;
  sum -= 15ll*(c+1)*c/2;      
  cout << sum << "\n";
}