1. Hey guys, 
    Hope you all are doing great. I am back with another problem of Project Euler on

    Project Euler #6: Sum square difference

    The sum of the squares of the first ten natural numbers is, 12+22+...+102=385. The square of the sum of the first ten natural numbers is, (1+2+⋯+10)2=552=3025. Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025−385=2640.
    Find the difference between the sum of the squares of the first N natural numbers and the square of the sum.
    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
    Print the required answer for each test case.
    Constraints
    1≤T≤104
    1≤N≤104
    Sample Input
    2
3
10
    Sample Output
    22
2640
    Algorithm:
    For this problem, i used a straight forward approach of summing the square of numbers and squaring the sum of numbers.
    Which has a time complexity of:
    O(N)
    It worked for this problem with the Python code and 2 of the test cases were passed.

    Not a Presto!! But yes its Pythoned!!

    Check my blow submission of Python Code. Do let me know if i can optimize it more.
    Program:


    t=input()
while(t>0):
    t-=1
    n=input()
    sum1 = sum([x**2 for x in xrange(1,n+1)])
    sum2 = sum(xrange(1,n+1))
    print sum2**2 - sum1
    Posted by
    Labels: Algorithms Hackerrank Hackerrank.com Mathematics Programming Project Euler Python
    1

    View comments

  2. Hey guys, 
    Hope you all are doing great. I am back with another problem of Project Euler on

    Project Euler #5: Smallest multiple


    2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
    What is the smallest positive number that is evenly divisible(divisible with no remainder) by all of the numbers from 1 to 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
    Print the required answer for each test case.
    Constraints
    1≤T≤10
    1≤N≤40
    Sample Input
    2
3
10
    Sample Output
    6
2520
    Algorithm:
     This problem is pretty simple, as we can see for instance we have n=10, so the series becomes
    1 2 3 4 5 6 7 8 9 10
    If we take the LCM of above the numbers
    which comes out to be computing the prime factors:
    1 = 1
    2 = 2
    3 = 3
    4 = 2*2
    5 = 5
    6 = 2*3
    7 = 7
    8 = 2*2*2
    9 = 3*3
    10 = 2*5
    So the LCM becomes (taking highest power of the factors) : 2*2*2*3*3*5*7 = 2520

    And Presto !! Its Done !!

    Now to convert the algorithm into python code, we can use a library function from fraction which is gcd. As we know 
    LCM of a and b = (a*b)/(gcd of a and b)

    And we can go to the code. heck below code as my submission.
    Program:


    from fractions import gcd
def lcm(a,b):
    return (a*b)//gcd(a,b)
t=input()
while(t>0):
    t-=1
    n=input()
    l=range(1,n+1)
    print reduce(lcm,l)
    Posted by
    Labels: Algorithms Hackerrank Hackerrank.com Mathematics Programming Project Euler Python
    0

    Add a comment

  3. Hey guys, 
    Hope you all are doing great. I am back with another problem of Project Euler on

    Project Euler #3: Largest prime factor

    The prime factors of 13195 are 5, 7, 13 and 29.
    What is the largest prime factor of a given number N?
    Input Format
    First line contains T, the number of test cases. This is followed by T lines each containing an integer N.
    Output Format
    For each test case, display the largest prime factor of N.
    Constraints
    1≤T≤10
    10≤N≤1012
    Sample Input
    2
10
17
    Sample Output
    5
17

    Algorithm:


    For finding prime numbers we need to check whether a number is not divisible by any number except 1 and itself.

    So as a brute force it is to iterate through all numbers less than it and check of the divisibility.

    But as we search for prime numbers < N, its time complexity will be
    O(N^2)


    Hence for large value brute force algorithm will fail.

    So we can find a pattern to decrease the number of iterations:

    As the first 5 prime numbers are 2, 3, 5, 7 and 11.
    We can filter the multiples of these, so number of iteration will become less than half

    Further,
    If a number n is not a prime, it can be factored into two factors a and b:
    n = a*b
    If both a and b were greater than the square root of n,  a*b would be greater than n. So at least one of those factors must be less or equal to the square root of n, and to check if n is prime, we only need to test for factors less than or equal to the square root.
    So in worst case the time complexity will be
    O(n*log(n))
    And Presto!! We are Done!!

    Now to program this in python, you need to take care of all conditions and make it work. Here is a snippet for my submission to the problem

    Program:


    import math
def is_prime(num): # Here you can add condition for exclusion of multiples of 2,3,5,7 & 11
 for j in range(2,int(math.sqrt(num)+1)):
  if (num % j) == 0: 
   return False
 return True
t=input()
while(t>0):
    t=t-1;
    n=input()
    for i in range(n,2,-1):
        if(n%i==0 and is_prime(i)):
            print i
            break;
    Posted by
    Labels: Algorithms Hackerrank Hackerrank.com Mathematics Programming Project Euler Python
    0

    Add a comment

  4. Hey Fellas!! So its time to roll on.
    Mathematical series are very interesting in there own ways. I find them interesting as they tickles your brain to know more.
    That you try to find the end. Counting on your fingers, you will get bored or either get tired.
    Programming!! Yeah that's interesting!!

    Lets begin this Series on Mathematical Series.

    One of the most popular, basic and interesting series is Fibonacci series:

     Probably the most famous of all Mathematical sequences; it goes like this—- 1,1,2,3,5,8,13,21,34,55,89…
    At first glance one may wonder what makes this sequence of numbers so sacrosanct or important or famous. However a quick inspection shows that it begins with two 1 s and continues to get succeeding terms by adding, each time, the last two numbers to get the next number (i.e., 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, and so on).
    The Fibonacci numbers can be found in connection with the arrangement of branches on various species of trees, as well as in the number of ancestors at every generation of the male bee on its family tree. There is practically no end to where these numbers appear or be sighted.
    Fibonacci numbers are very much connected to the famous ‘Golden Ratio’ or ‘Divine ratio’ whose value is equal to 1.618…
    There are many properties of Fibonacci series, only a few are listed below:
    i.            The sum of any ten consecutive Fibonacci numbers is divisible by 11.
    ii.            Two consecutive Fibonacci numbers do not have any common factor, which means that they are Co-prime or relatively prime to each other.
    iii.            The Fibonacci numbers in the composite-number (i.e., non-prime) positions are also composite numbers.
    iv.            The sum of the first n Fibonacci numbers is equal to the Fibonacci number two further along the sequence minus 1.Mathematically , F1  + F2+F3……..+Fn = Fn+2 -1.
    There are many counting problems in combinatorics whose solution is given by the Fibonacci Numbers.
    So let us code Fibonacci series in Python:
    n=input("Enter series limit")
    a,b=1,1
    print "Fibonacci Series:"
    print a,b,
    while(n-2>0):
        n-=1
        c=a+b
        print c,
        a,b=b,c
    Posted by
    Labels: First Post Mathematics Programming
    0

    Add a comment

  5. 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
    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        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&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
      Posted by
      Location: Hyderabad, Telangana, India
      Labels: Algorithms Hackerrank Hackerrank.com Mathematics Programming Project Euler Python
      0

      Add a comment

    Loading