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..
No comments:
Post a Comment