Question:Find the sum of even fibonacci numbers upto a limit N.

Input:100

Output:44

Fibonacci numbers are a miracle of Math and are defined as:-

f(0) = 0

f(1) = 1

f(n) = f(n-1) + f(n-2); for n>=2

Thus the Fibonacci series can be given as

0, 1, 1, 2, 3, 5, 8, 13, 21…

Let us try to understand the question. We need to find all the Fibonacci numbers till a limit ‘N’ and then sum only the even numbers in them.

Example:

*N = 10*

* Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8*

* Sum of even numbers: 2 + 8 = 10*

*N = 100*

* Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89*

* Sum of even numbers: 2 + 8 + 34 = 44*

If the value of ‘N’ is less than 10^6, this problem can be approached by a naive method of finding the Fibonacci numbers and then summing the even ones.

Surprisingly, there are very few even Fibonacci numbers till very large limits of N.

Have a look at the Fibonacci series and this interesting page about the first 300 Fibonacci numbers.

For this problem let us consider the maximum limit of N to be 10^16. That should be a pretty good limit. We need to understand the concept of pre-processing in this case. **Pre-processing** is used in scenarios where we can save a lot of computation power if we have some insight into what we are doing.

For example, here is a list of even Fibonacci numbers till 10^16. It is a very small list.

0 2 8 34 144 610 2584 10946 46368 196418 832040 3524578 14930352 63245986 267914296 1134903170 4807526976 20365011074 86267571272 365435296162 1548008755920 6557470319842 27777890035288 117669030460994 498454011879264 2111485077978050 8944394323791464 37889062373143906

Thus we just need to query this list for prime numbers till ‘N’

public class EvenFibonacciNumbers { public static void main(String[] args) { List<Long> evenFibonacciList = new ArrayList<>(); evenFibonacciList.add(0L); evenFibonacciList.add(2L); evenFibonacciList.add(8L); evenFibonacciList.add(34L); evenFibonacciList.add(144L); evenFibonacciList.add(610L); evenFibonacciList.add(2584L); evenFibonacciList.add(10946L); evenFibonacciList.add(46368L); evenFibonacciList.add(196418L); evenFibonacciList.add(832040L); evenFibonacciList.add(3524578L); evenFibonacciList.add(14930352L); evenFibonacciList.add(63245986L); evenFibonacciList.add(267914296L); evenFibonacciList.add(1134903170L); evenFibonacciList.add(4807526976L); evenFibonacciList.add(20365011074L); evenFibonacciList.add(86267571272L); evenFibonacciList.add(365435296162L); evenFibonacciList.add(1548008755920L); evenFibonacciList.add(6557470319842L); evenFibonacciList.add(27777890035288L); evenFibonacciList.add(117669030460994L); evenFibonacciList.add(498454011879264L); evenFibonacciList.add(2111485077978050L); evenFibonacciList.add(8944394323791464L); evenFibonacciList.add(37889062373143906L); Scanner scanner = new Scanner(System.in); int cases = scanner.nextInt(); for (int i = 0; i < cases; i++) { int N = scanner.nextInt(); long sum = 0; for (Long aLong : evenFibonacciList) { if (N > aLong) sum += aLong; else break; } System.out.println(sum); } scanner.close(); } }

You might also want to look at:

A working implementation of the code can be found here.

This problem can also be found on Hackerrank and ProjectEuler.

Time Complexity:

O(1)