PROBLEM LINK:
Author: Hanzala Sohrab
DIFFICULTY:
EASY-MEDIUM.
PREREQUISITES:
Math, Arithmetic progression
PROBLEM:
Find the sum of all the numbers less than or equal to N, that are either divisible by 3 or divisible by 5.
QUICK EXPLANATION:
Required sum = (Sum of all multiples of 3 less than or equal to N) + (Sum of all multiples of 5 less than or equal to N) - (Sum of all multiples of 15 less than or equal to N).
S = \sum_{i = 1}^{\left \lfloor{\frac{N}{3}}\right \rfloor}3i + \sum_{i = 1}^{\left \lfloor{\frac{N}{5}}\right \rfloor}5i - \sum_{i = 1}^{\left \lfloor{\frac{N}{15}}\right \rfloor}15i
EXPLANATION:
Total number of multiples of 3 less than or equal to N = \left \lfloor{\frac{N}{3}}\right \rfloor.
Greatest multiple of 3 less than or equal to N=3* \left \lfloor{\frac{N}{3}}\right \rfloor.
Total number of multiples of 5 less than or equal to N = \left \lfloor{\frac{N}{5}}\right \rfloor.
Greatest multiple of 5 less than or equal to N=5 *\left \lfloor{\frac{N}{5}}\right \rfloor.
Total number of multiples of 15 less than or equal to N = \left \lfloor{\frac{N}{15}}\right \rfloor.
Greatest multiple of 15 less than or equal to N=15 *\left \lfloor{\frac{N}{15}}\right \rfloor.
Sum of an arithmetic progression = \frac{n(a + l)}{2}, where
n is the total number of terms in the A.P.
a is the first term of the A.P.
l is the last term of the A.P.
Now, if we simply add all the multiples of 3 and 5, the multiples of 15 are added twice in the resulting sum. In order to get the correct sum, we must subtract the sum of all the multiples of 15 that are less than or equal to N.
So,
The sum of all multiples of 3 that are less than or equal to N= \frac{\left \lfloor{\frac{N}{3}}\right \rfloor \left(3 + 3* \left \lfloor{\frac{N}{3}}\right \rfloor \right)}{2}
The sum of all multiples of 5 that are less than or equal to N= \frac{\left \lfloor{\frac{N}{5}}\right \rfloor \left(5 + 5* \left \lfloor{\frac{N}{5}}\right \rfloor \right)}{2}
The sum of all multiples of 15 that are less than or equal to N= \frac{\left \lfloor{\frac{N}{15}}\right \rfloor \left(15 + 15* \left \lfloor{\frac{N}{15}}\right \rfloor \right)}{2}
Therefore, the required sum = \frac{\left \lfloor{\frac{N}{3}}\right \rfloor \left(3 + 3* \left \lfloor{\frac{N}{3}}\right \rfloor \right)}{2} + \frac{\left \lfloor{\frac{N}{5}}\right \rfloor \left(5 + 5 * \left \lfloor{\frac{N}{5}}\right \rfloor \right)}{2} - \frac{\left \lfloor{\frac{N}{15}}\right \rfloor \left(15 + 15* \left \lfloor{\frac{N}{15}}\right \rfloor \right)}{2}
COMPLEXITY:
Using iterative brute-force method - O(N)
Using the above given logic - O(1)
SOLUTIONS:
Setter's Solution
#include<iostream>
using namespace std;
int main() {
int t;
cin >> t;
while (t--)
{
// BRUTE-FORCE
// long long int i, s = 0, n;
// cin >> n;
// for (i = 1; i <= n; ++i)
// if (i % 3 == 0 and i % 5 != 0)
// s += i;
// else if (i % 5 == 0 and i % 3 != 0)
// s += i;
// else if (i % 15 == 0)
// s += i;
// cout<<s<<'\n';
// OPTIMAL
long long int n, n3 = 0, n5 = 0, n15 = 0;
cin >> n;
n3 = n / 3;
n5 = n / 5;
n15 = n / 15;
long s = (n3 * (6 + (n3 - 1) * 3)) / 2;
s += (n5 * (10 + (n5 - 1) * 5)) / 2;
s -= (n15 * (30 + (n15 - 1) * 15)) / 2;
cout << s << '\n';
}
return 0;
}