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 >= 2Code language: TeX (tex)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
37889062373143906Code language: TeX (tex)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();
}
}
Code language: Java (java)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)