Project Euler #315

Problem: Digital Root Clocks

Solution: [Spoiler Ahead]

       One of the easy problems and one of the easy solutions.
       It's just straight forward,

the number of LED on-off by SAM's clock - the number of LED on-off by MAX's clock

       Globals I used, a noOfLEDsForDigit[] array holding the number of led's required to glow a particular digit.
A digits[] array holding hex values for the number that represent the ON-OFF LED. e.g.

8 on 8

                    So finally, everything is completed and and perfect 8 on 8. I am now a Bachelor of Technology, what I would be liked to be called. After entering the CoEP and seeing all the brilliant students around I had thought that probably getting out of CoEP is more difficult than getting in.

           First Year: began with all the intros given to seniors(which I owe a  lot as it made me think that I didn't had anything special in me, I need to make myself into some or the other thing). The lectures went repeating some physics and chemistry part.Technically was introduced to the C-Programming which I even didn't know that this is going to be with my entire life henceforth. Even by the end of the first year, I didn't get to know the concept of a programming language, but I sored quite well in it(thanks to my friends, and this is the part where your friends help you a lot :P). As usual not to mention, when it comes to engineering Mathematics never leaves your collar bone. Bunked some lectures for the Regatta.

Aarz hai

Taaro ko ginne wale hum na the,
akele gungunane wale hum na the,
Ye to dosti aadat laga di,
varna kisi ko itna yaad karne wale hum na the.

Still trying to code ....

Introduced to programming language C and C++ in first year of my 4 year Engineering Course. Till the end of the year, I hardly understood the power of programming. But eventually the time spent dwindling with online tutorials in the summer break was a real break for me !!!

Spending next 6 months on data-structure, I got to know how to use the correct tool for the given problem, but many a times my decisions didn't gave any result. Codechef, Topcoders, Codeforces as proved a motivational platform to develop my skills.

Experience Bolta hai...

Last semester of engineering really taught me much more than I could perceive.My technical knowledge got boosted but on the other hand I got to know that we have to live a professional life in this professional world.

Bitter truth is something that one has to face at some point of time in your life.Once you start working on something, don't be afraid of failure and don't abandon it. People who work sincerely are the happiest.

Project Euler 5

Problem: What is the smallest number divisible by each of the numbers 1 to 20?

Solution: [Spoiler Ahead]

              I just checked for numbers that are divisible by all numbers between 11 and 20(inclusive), this algo is not much efficient but works well.

Toggle Code

Project Euler 4

Problem: Find the largest palindrome made from the product of two 3-digit numbers.

Solution: [Spoiler Ahead]

  The initial algorithm to the problem is : Check all products of two 3-digit number and store the required number.

Project Euler #3

Problem #3:Find the largest prime factor of a composite number.

Solution: 
As usual firstly the straight forward implementation. Run a loop and go on checking whether it divides the given number and check if it is prime, storing the largest one.

#include

#include"prime.h" //My own module,code not shown here

int main(){

long long num=600851475143L;

long largest_prime_factor=0,i;

for(i=10;i<num/2;i++)

if(num%i==0)

if(isPrime(i)) //return true if prime

largest_prime_factor=i;

printf("Answer to Euler #3 : %ld",largest_prime_factor);

return 0;

}

                    This can be optimized a little by defining a new upper bound for the loop counter  and that would be square root of the given number.

                     More over 2 is a factor which if checked separately will make our life easy. Then we can increase the factor by step of 2.

                    A little more optimized algorithm is:

n="a large number"



if n mod 2=0



then



    n=n / 2



    lastFactor=2



    while n % 2=0



        n=n / 2



else



    lastFactor=1





    factor=3



    while n>1



         if n % factor=0



         then



                n=n / factor



         lastFactor=factor



         while n % factor=0



                n=n / factor



         factor+=2





output lastFactor

This is not the fully optimized solution but can be modified further. That left to you ;-)

Enjoy coding :-)

Project Euler 2

Problem #2:Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

Solution: A straight forward implementation in C for this problem can be as shown

#include
#define LIMIT 4000000
int main()
{
 long a=1, b=2, c=0, sum=0;
 sum = b;
 while(c < LIMIT ){
  c = a+b;
  if(c < 1000000)
  if(c%2 == 0)
   sum += c;
  a = b;
  b = c;
 }
 printf("\nAnswer to euler #2 : %ld\n",sum);
}

        
                 This code works fine for our required need, but more optimizations can be done.How? Lets look at the fibo seq.

                                                    1 1 2 3 5 8 13 21 34 55 89 144 ...

                 As we can see,every 3rd term is a even number. Therefore we can change the code accordingly to just sum up every third number.
                 Another approach is we can find a recurrence funtion for this new series i.e. we can have :

F`(n)=4*F`(n-1) + F`(n-2)

It is easy to prove that for Fibonacci series we get:

 F(n)=4*F(n-3)+F(n-6) 

Thus we get a more faster running code, which we eventually need :-)

Enjoy coding :-)

My all time favourite Movies

Mughal-e-azam

A Wednesday

Munnabhai M.B.B.S

Swades - we the people

Dil Chahta Hai

Rang De Basanti

Project Euler 1

Problem #1. Add all the natural numbers below one thousand that are multiples of 3 or 5.

Solution : This can be done in two ways ....

i. The normal method, i.e. run a for from 1 to 1000 and check for the given condition on each number.

This method does solves our problem but is crude.

upperlimit=999
total_sum=0
for i=1 to upperlimit do
if (i mod 3=0) or (i mod 5)=0 then
total_sum:=total_sum+i;
output total_sum

ii. The short-cut method : In this you need only one formula and just need to compute value of 3 expressions.

Just go through---->

The solution to given problem will be the answer of this expression :

ans = sumDivisibleBy(3) + sumDivisibleBy(5) - sumDivisibleBy(15)

Now for n=3 :

3,6,9,12,15,18,21,24,27,.....,999 = 3(1,2,3,4,5,6,7,8,9,....,333)

Now we know that :

1 + 2 + 3 + .... + q = 1/2*q*(q+1)

In our case : q = upperlimit / n

Therefore our solution says :

Function sumDivisibleBy(n):
q = upperlimit div n
return n*(q*(q+1)) div 2
EndFunction

print sumDivisibleBy(3)+sumDivisibleBy(5)-sumDivisibleBy(15)

Feel free to ask any kind of querry, I'll try my best to solve it.

Enjoy coding :-)