For a given positive integer N, the purpose is to find the value of F2 + F4 + F6 +………+ F2n till N number. Where Fi indicates the i’th Fibonacci number.
The Fibonacci Series is the numbers in the below-given integer sequence.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ……
Examples:
Input: n = 4 Output: 33 N = 4, So here the fibonacci series will be produced from 0th term till 8th term: 0, 1, 1, 2, 3, 5, 8, 13, 21 Sum of numbers at even indexes = 0 + 1 + 3 + 8 + 21 = 33. Input: n = 7 Output: 609 0 + 1 + 3 + 8 + 21 + 55 + 144 + 377 = 609.
Approach 1:
Find all Fibonacci numbers till 2n and add up only the even indices.
Java
// Java Program to find even sum of// fibonacci Series Till number Nimport java.io.*;class neveropen { // Computing the value of first fibonacci series // and storing the sum of even indexed numbers static int Fib_Even_Sum(int N) { if (N <= 0) return 0; int fib[] = new int[2 * N + 1]; fib[0] = 0; fib[1] = 1; // Initializing the sum int s = 0; // Adding remaining numbers for (int j = 2; j <= 2 * N; j++) { fib[j] = fib[j - 1] + fib[j - 2]; // Only considering even indexes if (j % 2 == 0) s += fib[j]; } return s; } // The Driver code public static void main(String[] args) { int N = 11; // Prints the sum of even-indexed numbers System.out.println( "Even sum of fibonacci series till number " + N + " is: " + +Fib_Even_Sum(N)); }} |
Even sum of fibonacci series till number 11 is: 28656
Time Complexity: O(n)
Auxiliary Space: O(n) as it is using an auxiliary array fib
Approach 2:
It can be clearly seen that the required sum can be obtained thus:
2 ( F2 + F4 + F6 +………+ F2n ) = (F1 + F2 + F3 + F4 +………+ F2n) – (F1 – F2 + F3 – F4 +………+ F2n)Now the first term can be obtained if we put 2n instead of n in the formula given here.
Thus F1 + F2 + F3 + F4 +………+ F2n = F2n+2 – 1.
The second term can also be found if we put 2n instead of n in the formula given here
Thus, F1 – F2 + F3 – F4 +………- F2n = 1 + (-1)2n+1F2n-1 = 1 – F2n-1.
So, 2 ( F2 + F4 + F6 +………+ F2n)
= F2n+2 – 1 – 1 + F2n-1
= F2n+2 + F2n-1 – 2
= F2n + F2n+1 + F2n+1 – F2n – 2
= 2 ( F2n+1 -1)
Hence, ( F2 + F4 + F6 +………+ F2n) = F2n+1 -1 .
The task is to find only F2n+1 -1.
Below is the implementation of the above approach:
Java
// Java Program to find even indexed// Fibonacci Sum in O(Log n) time.class GFG { static int MAX = 1000; // Create an array for memoization static int f[] = new int[MAX]; // Returns n'th Fibonacci number // using table f[] static int fib(int n) { // Base cases if (n == 0) { return 0; } if (n == 1 || n == 2) { return (f[n] = 1); } // If fib(n) is already computed if (f[n] == 1) { return f[n]; } int k = (n % 2 == 1) ? (n + 1) / 2 : n / 2; // Applying above formula [Note value n&1 is 1 // if n is odd, else 0]. f[n] = (n % 2 == 1) ? (fib(k) * fib(k) + fib(k - 1) * fib(k - 1)) : (2 * fib(k - 1) + fib(k)) * fib(k); return f[n]; } // Computes value of even-indexed Fibonacci Sum static int calculateEvenSum(int n) { return (fib(2 * n + 1) - 1); } // Driver program to test above function public static void main(String[] args) { // Get n int n = 11; // Find the alternating sum System.out.println( "Even indexed Fibonacci Sum upto " + n + " terms: " + calculateEvenSum(n)); }} |
Even indexed Fibonacci Sum upto 8 terms: 1596
Time Complexity: O(log n)
Auxiliary Space: O(MAX) because using an auxiliary array
