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

Loading