#### Problem 2: Even Fibonacci Numbers

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.

#### The Catch

How to efficiently generate a Fibonacci sequence.

How to pick out the even-valued Fibonacci number.

#### The Light

The recursive approach to generating a Fibonacci sequence (time complexity of **O(2 ^{n})**) might not be as elegant as an iterative one. Consider this piece of code, which prints all Fibonacci numbers under 10 using the iterative approach (time complexity of

**O(n)**). For every fibonacciNumber created, check if it is divisible by 2 to pick out the even-valued ones. Sum them up to find the answer.

int firstNumber = 1; int secondNumber = 2; int fibonacciNumber = 0; System.out.print(firstNumber + " " + secondNumber); while(fibonacciNumber < 10) { fibonacciNumber = firstNumber + secondNumber; System.out.print(" " + fibonacciNumber); firstNumber = secondNumber; secondNumber = fibonacciNumber; }

#### The Code

public class Problem2 { public static void main(String[] args) { fib(); } public static void fib() { int f1 = 1; int f2 = 1; int fib = 0; int sum = 0; while(fib < 4000000) { fib = f1 + f2; if(fib % 2 == 0) sum += fib; f1 = f2; f2 = fib; } System.out.println(sum); } }