Problem 4: Largest palindrome number

Q.Find the largest palindrome number made from the product of two 3-digit numbers.


Sol.
The problem can be solved easily by brute force i.e. checking all the products of 3-digit numbers to be palindrome and then determining the largest among them.
The code for palindrome checking is easy, we can simply reverse the number and check the equality.
int ispalindrome(int n)
{
        int temp=n,rem,sum;
        while(n>0)
        {
              rem=n%10;
              n=n/10;
              sum=sum*10 + rem;
         }
         if(sum==temp)
              return 1;
         else
              return 0;
}


int main()
{
      int big=0;
      for(i=999;i>=100;i--)
          for(i=999;i>=100;i--)
              if(ispalindrome(i*j)&&(big<(i*j)))
                         big=(i*j);
}
As you may have noticed, it takes too much time. So, I used some of my observations regarding the problem to reduce the time.


1. A palindrome number with even number of digits is always divisible by 11. So, at least  one of the numbers must be divisible by 11.Thus the inner loop can be decreased to be decremented by 11 each time.
2.There are many redundant multiplications like 999*998 and then 998*999.That must be reduced.For that we can find the nearest number to 'i' which is divisible by 11 and is less than 'i'.
It can be done easily as the number would be : i-(i%11)
3. The last digit of the palindrome number can't be zero as the first isn't. So, all the numbers which are multiple of 10 can be eliminated from the consideration.


The improved code can be:
int main()
{
         int big=0,i,j;
         for(i=999;i>=101;i--)
         {
                   if(i%10==0)
                          continue;
                   x=i-(i%11);
                   for(j=x;j>=121;j-=11)
                   {
                            n=i*j;
                            if(ispalindrome(n)&& big < n)
                                   big=n;
                   }
          }
          printf("%d",big);
}


Please post your comments and doubts...
Suggestion for better algorithms are always welcome.....
This is me signing off for today....

Problem 3: Largest Prime Factor

Q. What is the largest prime factor of the number 600851475143 ?


Sol:
It can be seen that the largest prime factor of a number is equal to larger of its largest prime factor of its largest factor and the smallest factor.
i.e. largest prime factor(n)=max(smallest factor(n), largest prime factor(largest factor(n)))
or,largest prime factor(n)=max(smallest factor(n), largest prime factor(n/smallestfactor(n)))


using the relation, either the recursive or the iterative approach can be applied to solve the problem..


Now, it can also be seen that while finding the smallest factor, we only need to divide the number concerned by only one even number '2' and rest can be odd numbers. So, all the other even numbers can be eliminated from the process, thus optimizing our program. 
Since, a factor 'i' can divide 'n' multiple times, we can also put a subroutine to divide n by i multiple times until the new number comes out to be not divisible by i, further optimizing the problem...


Now the last and the easiest part , Coding :



long long int solution(long long n)
{

     int i=2;
     long long x;
     if(n%2==0)
     {
               x=n/i;
               while(x%i==0)
                            x=x/i;
               x=solution(x);
               return((i>x)?i:x);
     }
     else
     {
         i=3;    
         while(i < sqrt ( ( double ) n ) )
         {
                                 if(n%i==0)
                                 {
                                           x=n/i;
                                           while(x%i==0)
                                                        x=x/i;
                                           x=solution(x);
                                           return((i>x)?i:x);
                                 }
                                 i=i+2;
         }
         return n;
     }
}



As explained above, the code applies recursive approach to solve the problem and returns the largest prime factor for 'n'..

Please post your comments and doubts...

Better algorithms are always welcome..

Problem 2: Sum of even fibonacci numbers

Q.Find the sum of all the even-valued terms in the sequence which do not exceed four million.


Sol:
This problem too is a trivial one if the brute force approach is followed. But on observing the fibonacci series, it is observed that there is an even number every three steps....
1 1 2 3 5 8 13 21 34 55 89 144 .......
So, instead of checking for divisibility by 2 each time an element is calculated, every third fibonacci number can be added upto 4 million to find the result.

The code to solve the problem can then be :

   i=1,j=2,d=0,x=0;
   long s=0;
   while(j<4000000)
   {
            s=s+j;
            while(d<=2)
            {
                       x=i+j;
                       i=j;
                       j=x;
                       d++;
            }
            d=0;           
   }
   cout << s
}

As explained, the code calculates three elements in each loop and adds the third number to the sum.

Please post your comments...
Better algorithms are always welcome..

Problem 1 : Sum of numbers

Q. Find the sum of all the multiples of 3 or 5 below 1000.

Sol:
This one must be the easiest problem on Euler.. It can be solved easily without programming.
For an arithmetic progression whose first term is 'a', last term is 'l' and no. of elements is n, the sum is given by
n/2 * (a+d).
So, since we are required to calculate the sum of numbers up to 1000 divisible by either 3 or 5, we just calculate the sum of numbers divisible by 3(S1) and add it to sum of numbers divisible by 5(S2).Now taking care that those divisible by both 3 and 5(i.e. those divisible by 15) have been summed up twice,we subtract the sum of numbers divisible by 15(S3) from it. Nice and easy!!!!

No. of numbers divisible by 3=999/3=333
S1= 333/2 * (3+999)=166833
No. of numbers divisible by 5=995/5=199
S2=199/2 * (5+995)=99500
NO. of numbers divisible by 15= 990/15=66
S3=66/2 * (15+990)=33165

Result= S1 + S2 -S3= 233168

Please post your comments...
Better algorithms are always welcome..

I start euler........

Today, I finally started solving problems on project euler.I am really a very lazy person, so when I started it, I thought there must be some way of keeping me doing it. Maybe writing a blog on it will help,because if there are no more questions to solve, then how will I continue my blog....
So, here it is..
My adventure on Project Euler....