Kurtesy of a Coder: May 2015

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:

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

Input Format
First line contains

T that denotes the number of test cases. This is followed by

T lines, each containing an integer,

Output Format
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:

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.

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 S_n = (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:

Program:

t=input()
while(t&gt;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

Kurtesy of a Coder

I have been extensively involved in online coding, core programming, algorithmic puzzles, maze of syntax and as all time hobby of coding, Whether its Hacker, Chef, Earth or Top-Jam, hitting on some basic and some most tricky problems.

Project Euler+ #1

Project Euler #1: Multiples of 3 and 5

Algorithm:

Add a comment