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 N.
Input Format
First line contains T that denotes the number of test cases. This is followed by T lines, each containing an integer, N.
Output Format
For each test case, print an integer that denotes the sum of all the multiples of 3 or 5 below N.
Constraints
1T105
1N109
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 
     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:
    Program:
    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
    
    0

    Add a comment

    Loading