Project Euler Multiples of 3 and 5

general
1

I am solving this problem:[link][1]
Here’s my solution:

#include<iostream>

using namespace std;


int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        long long mul_5, mul_3, mul_15, n, sum;
        cin>>n;
        mul_5 = 5 * (n/5 * (n/5+1))/2;
        mul_3 = 3 * (n/3 * (n/3+1))/2;
        mul_15 = 15 * (n/15 * (n/15+1))/2;
        sum = mul_5 + mul_3 - mul_15; // AP of 3 and 5 minus 15 to remove duplicates
        cout<<sum<<endl;
    }
    return 0;
}

The output gives wrong answer. Help
[1]: Project Euler #1: Multiples of 3 and 5 | HackerRank

2

What approach did you use dear? Also, did you consider the traditional Arithematic Progression approach?

Here is my code if you want to have a look -

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int t; 
    scanf("%d",&t);
    for(int a0 = 0; a0 < t; a0++){
        int n; 
        scanf("%d",&n);
        long int counter=0,i,j,k,t3,t5,t15;
        t3=(n-1)/3;//number of terms of 3
        t5=(n-1)/5;//number of terms of 5
        t15=(n-1)/15;//number of terms of 15
        i=t3*(6+(t3-1)*3);//formula for sum of an AP- Sum= n/2 x (2a+(n-1)d)
        j=t5*(10+(t5-1)*5);
        k=t15*(30+(t15-1)*15);
        counter=(i+j-k)/2;//counter stores the final ans. IDK why I named it that XD
        printf("%ld\n",counter);
    }
    return 0;
}

EDIT-

Here is the corrected code-

#include<iostream>

using namespace std;


int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        long long mul_5, mul_3, mul_15, n, sum=0;
        cin>>n;
        mul_5 = 5 * ( (n-1)/5 * ( (n-1)/5+1))/2;
        mul_3 = 3 * ( (n-1)/3 * ( (n-1)/3+1))/2;
        mul_15 = 15 * ( (n-1)/15 * ( (n-1)/15+1))/2;
        sum = mul_5 + mul_3 - mul_15; // AP of 3 and 5 minus 15 to remove duplicates
        cout<<sum<<endl;
    }
    return 0;
}

You were doing a mistake in calculating the number of terms. The question says that the term must be STRICTLY less than N. Your code also included N.

Meaning, if N=10, your code gives 2 multiples of 5 in the range (5 and 10) while it should be one. Its easily corrected by subtracting 1 from N and then using it as usual.

2 Likes
3

Well. One more additional information, the original link of Project Euler problem is Link. It contains series of brainstorming problems. If you can solve 120+, it will increase your chances of being selected in mathematics and computing courses in foreign universities.

1 Like
4

The problem says below n but in your case you count n as well. You must do n-- after taking n as input.
Rest is fine. :slight_smile:
AC code: https://www.hackerrank.com/contests/projecteuler/challenges/euler001/submissions/code/1301053442

2 Likes
5

Thanks as always!

1 Like
6

True. BTW, I heard that hackerrank added some test cases and its better to do it from there. Any idea about that?

7

Hackerrank have somewhat more solved problems of euler project. It is anyways good for competitive thinking aptitude building but this may not fetch you acceptance in foreign university(IVY League). I mean typical less solved problems. :slight_smile:

8

@vijju123 My maths is really weak. Sometimes, I couldn’t​ make out the obvious calculations from ad hoc problems. Hence, I’v started solving Project Euler’s problems on Hackerrank and got stuck on the very first problem. Can you suggest me few more sites like this to sharpen my skills.

9

Its actually better to use resources of one site properly than to solve random stuff from 10 sites. Because when you see project euler, you will see how it slowly progresses from basic to advance. Also, your application of maths and concepts were correct, you just mis-read the problem statement. Don’t worry that much, you are doing fine.

If anything, you can also look at previous problems in contests like AD Infinitum on hackerrank, as they contain problems especially related to Maths. Don’t worry, take small steps and you will soon find yourself taking big leaps. :slight_smile:

1 Like
10

Well. If you really want to start working on maths(for competitive programming perspective) the project euler is very tough choice. The level of questions require bit more than maths. I have seen some problems which can give brainfreeze( i.e. got accepted in C++ but gives TLE in python and JAVA due to costly I/O). Also I completely agree with @vijju123.I will suggest you to solve problems from Hackerearth in math section. Link

2 Likes