2
\$\begingroup\$

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.

I wrote a solution to this second problem from Project Euler, and would appreciate a review of it. Here's the code:

package Problems.Level_1;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by Manish on 10/14/2015.
 * find sum of even terms of Fibonacci series whose values do not exceed four million
 */
public class Problem_2 {

    private List<Integer> generateFibonacci() {
        List<Integer> numbers = new ArrayList<>();
        int first = 1;
        int last = 2;
        numbers.add(first);
        numbers.add(last);
        int sum = 0;
        //modify for loop to limit value = 4 mil?
        //for(int i = 2; i < limit; i++)
            while(sum <= 4000000){
            sum = first + last;
            numbers.add(sum);
            first = last;
            last = sum;
        }

        return numbers;
    }

    //method to generate int array from a List of integers
    private int[] buildIntArray(List<Integer> integers) {
        int[] ints = new int[integers.size()];
        int i = 0;
        for (Integer n : integers) {
            ints[i++] = n;
        }
        return ints;
    }

    //method to calculate sum of even items in array
    private int calculateEvenSum(int[] numList){
        int result = 0;
        for(int i = 0; i < numList.length; i++) {
            if(numList[i] % 2 == 0) {
                result += numList[i];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Problem_2 p2 = new Problem_2();

        //System.out.println("The first 10 numbers of the Fibonacci Series are: " + p2.generateFibonacci(10));
        //System.out.println("Enter the limit.");
       // int l = new Scanner(System.in).nextInt();

        List<Integer> list = p2.generateFibonacci();
        int[] numList = p2.buildIntArray(list);
        int answer = p2.calculateEvenSum(numList);

        System.out.println("The sum is: " + answer);
    }
}

Right off the bat, I get that it might not be the best idea to generate an entire Fibnoacci sequence, the sum can probably be determined without that. Then there might be things like creating and storing a List, creating and storing an array from the List, etc.

Does this solution cause too much of an unnecessary overhead?

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

Yes, it is unnecessary to create a sequence, then add it. Just simply add while counting up. Take a look at my question and this answer; it will simply create the sequence while adding, without even having to store the sequence, just the result and the previous numbers. It takes the advantage of the fact that every three Fibonacci numbers in the sequence is an even number, so inside the while loop, all it needs to do, is add the result, then skip 2 numbers. The code (for convenience) is down below:

public class EvenFibonacciFinder {
    private static final int MAX_NUM = 4_000_000;

    public static void main(String[] args)
    {
        long time = System.nanoTime();
        int fib1 = 1;
        int fib2 = 2;
        long sum = 0;

        while (f2 <= MAX_NUM) {
            int fib3;
            sum += fib2;
            // This skips three ahead in the sequence.
            fib3 = fib1 + fib2;
            fib1 = fib2 + fib3;
            fib2 = fib1 + fib3;
        }
        long end = System.nanoTime();
        System.out.println("Result: " + sum +
                "\nTime used for calculation in nanoseconds: " +
                (end - time));
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.