One of the Popular contest in Hackerrank based on a famous site ProjectEuler.net is
Project Euler+
Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.
So its a lonng contest with pretty big number of questions to be solved.
Coming forth i will be posting the Algorithms and Solutions on Python which i have used to solve the problems.
I go by the name of nis1992 you can check my profile here: https://www.hackerrank.com/nis1992
Lets start with the first Problem:
To solve this problem, a direct approach to check whether a number in the range is divisible
by 3 or 5, using the modulus operator.
As we know the sum of AP is Sn = (n/2)[2a +(n -1)d]
Similarly for 2nd and 3rd Case it becomes:
And Presto!! Its Done!!
Just we need to convert that into a code, which is easy ion Python, Check the below code:
Program:
Project Euler+
Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.
So its a lonng contest with pretty big number of questions to be solved.
Coming forth i will be posting the Algorithms and Solutions on Python which i have used to solve the problems.
I go by the name of nis1992 you can check my profile here: https://www.hackerrank.com/nis1992
Lets start with the first Problem:
Project Euler #1: Multiples of 3 and 5
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 N .
Input Format
First line containsT that denotes the number of test cases. This is followed by T lines, each containing an integer, N .
First line contains
Output Format
For each test case, print an integer that denotes the sum of all the multiples of 3 or 5 belowN .
For each test case, print an integer that denotes the sum of all the multiples of 3 or 5 below
Constraints
1≤T≤105
1≤N≤109
Sample Input
2
10
100
Sample Output
23
2318
Algorithm:
But as the Time complexity for the program will be O(N), where N is the input, if become large,
our program will take a large time to execute.
Hence we will use some mathematics to solve this.
So if i break the problem in to 3 parts:
- Sum of numbers divisible by 3 :- 3+6+9+12......
- Sum of numbers divisible by 5 :- 5+10+15+20.....
- Sum of numbers divisible by 15 :- 15+30+45.....
We took the case of multiples of 15 as we will encounter cases where we add numbers divisible by both 3 and 5 hence to remove the duplicate values.
As we know the sum of AP is Sn = (n/2)[2a +(n -1)d]
So for the 1st Case:
a=3, d=3
hence sum becomes: S(n) = (n/2)[2*3 + (n-1)*3]
Similarly for 2nd and 3rd Case it becomes:
S(n) = (n/2)[2*5 + (n-1)*5]
and
S(n) = (n/2)[2*15 + (n-1)*15]
And Presto!! Its Done!!
Just we need to convert that into a code, which is easy ion Python, Check the below code:
t=input() while(t>0): n=input() n-=1 n3=int(n/3) n5=int(n/5) n15=int(n/15) t-=1 sum=(n3 * (2*3 + (n3-1)*3))/2 sum1=(n5 * (2*5 + (n5-1)*5))/2 sum3=(n15 * (2*15 + (n15-1)*15))/2 print sum+sum1-sum3
Add a comment