We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #1: Multiples of 3 and 5
  4. Discussions

Project Euler #1: Multiples of 3 and 5

  • halfway_there1
     + 0 comments

    If you approached the question using AP and have removed the repeating elements (i.e., sum of multiples of 15) from the: sum of AP of 3 + sum of AP of 5, then the only thing you need to make sure is that integer overflow does not occur. This is the reason why your testcases 2 & 3 might not pass. One trivial way to ensure that integer overflow doesn't occur is to use long long int for every variable. Another way is to type cast befor overflow occurs for storing the intermediate values. Here's my solution for your reference.

    #include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;


int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        long long int n;
        cin >> n;
        long long int a = (n - 1) / 3;
        long long int b = (n - 1) / 5;
        long long int sum = a * (3 + 3 * a) >> 1;
        sum += b * (5 + 5 * b) >> 1;
        long long int c = (n - 1) / 15;
        sum -= c * (15 + 15 * c) >> 1;
        cout << sum << "\n";
    }
    return 0;	
		
}