CODEWITHSUNDEEP
java
user23463
user23463

Reputation: 27

Project Euler no. 2

I took many stabs at it and I can't seem to figure out what I am doing wrong. That is one of my most recent attempts at a solution.

I know the correct answer from other sources is 4613732.

/*
 *             PROBLEM 2
 * Each new term in the Fibonacci sequence is generated by adding the previous two terms. 
 * By starting with 1 and 2, the first 10 terms will be:
 *
 * 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
 *
 * By considering the terms in the Fibonacci sequence whose values do not exceed four 
 * million, find the sum of the even-valued terms.
 */

public class problem2 
{
    public static void main(String args[])
    {
        int sum = 0;

        int[] anArray = new int[4000000];
        anArray[0] = 1;
        anArray[1] = 2;

        for (int i = 2; i <= anArray.length - 1; i++) {
            anArray[i] = anArray[i - 1] + anArray[i - 2];

            if (anArray[i] % 2 == 0 && anArray[i] <= 4000000) {
                sum += anArray[i];
            }
        }
        System.out.println(sum);        
    }
}

Upvotes: 1

Views: 424

Answers (6)

ChrisOdney
ChrisOdney

Reputation: 6384

If you observe the fibonacci sequence, every third number is a even number:

1,1,2,3,5,8,13,21,34

So an array of length 3 will suffice. We can generate the next 3 fibonacci numbers and store it(overwrite) in the array, the sum of all the third elements(even fib number) in the array will give us the sum of all even numbers in the fibonacci sequence.

Code:

public class Prob2 {
    public static int sumOfEvenFibonacci(int limit){
        int fibonacci[] = {1, 1, 2}; 
        int j, sum = 2;

        while(fibonacci[2] < limit){
            for(j = 0; j < 3; j++){
                fibonacci[j] = fibonacci[(j+1)%3] + fibonacci[(j+2)%3];
            }
            sum += fibonacci[2];
        }
        return sum - fibonacci[2];
    }
}

Trivial test cases:

public class TestProb2 {

@Test
public void testSumOfMultiples(){
    int actual = Prob2.sumOfEvenFibonacci(15);
    assertEquals(10, actual);

    actual = Prob2.sumOfEvenFibonacci(50);
    assertEquals(44, actual);

    actual = Prob2.sumOfEvenFibonacci(200);
    assertEquals(188, actual);

    actual = Prob2.sumOfEvenFibonacci(4000000);
    assertEquals(4613732, actual);
}

}

P.S: This answer may not exactly answer the OP's question but wanted to share the technique out of joy of finding it. Hope it helps others who land here looking for a solution.

Upvotes: -1

Deepeshkumar
Deepeshkumar

Reputation: 443

Using an array instead of writting some formula for the sum makes the solution of the problem very ordinary.You can simply use the equal to arithmatic operator, smartly to avoid using an array. My code solution is like this. Hope it helps you.

       /*PRoject euler problem2*/
       /*Sum of even terms in fibonacci sequence*/
           public class Euler2
             {

                static long fibosum()
                 {
                    long sum=0;
                    long initialint=0;
              long secondint=1;
              long fibo=initialint+secondint;
                while(fibo<4000000)
                  {
                    if(fibo%2==0)
                {
                  sum=sum+fibo;
                }
                         initialint=secondint;
                   secondint=fibo;
                   fibo=initialint+secondint;
                        }
             return sum;
               }
             public static void main(String args[])
              {
                 Euler2 a=new Euler2();
           System.out.println("Sum of even fibonacci numbers below 4000000 is"+a.fibosum());
               }
  }

Upvotes: 0

Antimony
Antimony

Reputation: 39451

The logic looks correct to me, however it is an inefficient approach. Project Euler is designed to make you figure out better algorithms, so it is likely that your naive algorithm is running out of time or memory.

Try looking for patterns in the fibonacci numbers to come up with a faster approach.

Edit: I missed that you aren't breaking out of the loop after reaching 4000000. In this case the numbers will overflow and give you incorrect results. You need to break after the numbers exceed 4000000. Also, that huge array is completely unnecessary since you only need the last two numbers to calculate each new number.

Upvotes: 0

Jon Lin
Jon Lin

Reputation: 143906

You're exceeding the precision of an int. You're calculating way too many numbers, and eventually get negative numbers. Make the size of your array something sane (like 40), or make a check in your if statement to ignore negative numbers.

Actually, just change the size of the array to 40, since anything after int flips is wrong.

int [] anArray = new int[40];

Also note that you are not adding the 2, the second number in your array.

You can also just break out of the for loop when your numbers exceed 4,000,000, since you don't care about them anyways.

Upvotes: 1

dspyz
dspyz

Reputation: 5510

First, you're missing the two Second, to avoid issues with overflow: http://en.wikipedia.org/wiki/Integer_overflow, you should insert a break statement as soon as it goes over a million.

Upvotes: 1

zw324
zw324

Reputation: 27200

for(int i=2;i<=anArray.length-1;i++){
            anArray[i]=anArray[i-1]+anArray[i-2];

            if(anArray[i]%2==0 && anArray[i]<=4000000){
                    sum+=anArray[i];
            }
        }

You should check the limit of Fibonacci numbers in the loop, not just in the "sum" part. Because you are missing the check, you overflowed. After the overflow, the number "wrapped" back to smaller numbers, causing them (possibly, but definitely here) to be smaller than 4000000.

You can use BigInteger to avoid overflow here. It does not have great performances (at least for Java 1.6), but it'll work with this problem.

Upvotes: 0

Related Questions