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

    Popular Posts
    Popular Posts
    print ("About Me")
    print ("About Me")
    My Photo
    HYDERABAD, Telangana, India
    Blog.History(All)
    Labels
    Total Pageviews
    Total Pageviews
    21466
    About Me
    About Me
    Loading
    Dynamic Views theme. Powered by Blogger. Report Abuse.