Given a positive integer N, the task is to find the value of F2 + F4 + F6 +………+ F2n upto N terms where Fi denotes the i-th Fibonacci number.
The Fibonacci numbers are the numbers in the following integer sequence.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……
Examples:
Input: n = 5
Output: 88
N = 5, So the fibonacci series will be generated from 0th term upto 10th term:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Sum of elements at even indexes = 0 + 1 + 3 + 8 + 21 + 55
Input: n = 8
Output: 1596
0 + 1 + 3 + 8 + 21 + 55 + 144 + 377 + 987 = 1596.
Method-1: This method includes solving the problem directly by finding all Fibonacci numbers till 2n and adding up the only the even indices. But this will require O(n) time complexity.
Below is the implementation of the above approach:
C++
// C++ Program to find sum// of even-indiced Fibonacci numbers#include <bits/stdc++.h>using namespace std;// Computes value of first fibonacci numbers// and stores the even-indexed sumint calculateEvenSum(int n){ if (n <= 0) return 0; int fibo[2 * n + 1]; fibo[0] = 0, fibo[1] = 1; // Initialize result int sum = 0; // Add remaining terms for (int i = 2; i <= 2 * n; i++) { fibo[i] = fibo[i - 1] + fibo[i - 2]; // For even indices if (i % 2 == 0) sum += fibo[i]; } // Return the alternating sum return sum;}// Driver program to test above functionint main(){ // Get n int n = 8; // Find the even-indiced sum cout << "Even indexed Fibonacci Sum upto " << n << " terms: " << calculateEvenSum(n) << endl; return 0;} |
Java
// Java Program to find sum// of even-indiced Fibonacci numbersimport java.io.*;class GFG {// Computes value of first fibonacci numbers// and stores the even-indexed sumstatic int calculateEvenSum(int n){ if (n <= 0) return 0; int fibo[] = new int[2 * n + 1]; fibo[0] = 0; fibo[1] = 1; // Initialize result int sum = 0; // Add remaining terms for (int i = 2; i <= 2 * n; i++) { fibo[i] = fibo[i - 1] + fibo[i - 2]; // For even indices if (i % 2 == 0) sum += fibo[i]; } // Return the alternating sum return sum;}// Driver program public static void main (String[] args) { // Get n int n = 8; // Find the even-indiced sum System.out.println("Even indexed Fibonacci Sum upto " + n + " terms: "+ + calculateEvenSum(n)); }}// This code is contributed// by shs |
Python 3
# Python3 Program to find sum # of even-indiced Fibonacci numbers # Computes value of first fibonacci# numbers and stores the even-indexed sum def calculateEvenSum(n) : if n <= 0 : return 0 fibo = [0] * (2 * n + 1) fibo[0] , fibo[1] = 0 , 1 # Initialize result sum = 0 # Add remaining terms for i in range(2, 2 * n + 1) : fibo[i] = fibo[i - 1] + fibo[i - 2] # For even indices if i % 2 == 0 : sum += fibo[i] # Return the alternating sum return sum# Driver codeif __name__ == "__main__" : # Get n n = 8 # Find the even-indiced sum print("Even indexed Fibonacci Sum upto", n, "terms:", calculateEvenSum(n))# This code is contributed # by ANKITRAI1 |
C#
// C# Program to find sum of // even-indiced Fibonacci numbers using System;class GFG{ // Computes value of first fibonacci// numbers and stores the even-indexed sum static int calculateEvenSum(int n) { if (n <= 0) return 0; int []fibo = new int[2 * n + 1]; fibo[0] = 0; fibo[1] = 1; // Initialize result int sum = 0; // Add remaining terms for (int i = 2; i <= 2 * n; i++) { fibo[i] = fibo[i - 1] + fibo[i - 2]; // For even indices if (i % 2 == 0) sum += fibo[i]; } // Return the alternating sum return sum; } // Driver Code static public void Main (){ // Get n int n = 8; // Find the even-indiced sum Console.WriteLine("Even indexed Fibonacci Sum upto " + n + " terms: " + calculateEvenSum(n)); } } // This code is contributed// by Sach_Code |
Javascript
<script>// Javascript Program to find sum// of even-indiced Fibonacci numbers // Computes value of first fibonacci numbers // and stores the even-indexed sum function calculateEvenSum( n) { if (n <= 0) return 0; let fibo = Array(2 * n + 1); fibo[0] = 0; fibo[1] = 1; // Initialize result let sum = 0; // Add remaining terms for ( i = 2; i <= 2 * n; i++) { fibo[i] = fibo[i - 1] + fibo[i - 2]; // For even indices if (i % 2 == 0) sum += fibo[i]; } // Return the alternating sum return sum; } // Driver program // Get n let n = 8; // Find the even-indiced sum document.write("Even indexed Fibonacci Sum upto " + n + " terms: " + +calculateEvenSum(n));// This code is contributed by 29AjayKumar </script> |
PHP
<?php// PHP Program to find sum of // even-indiced Fibonacci numbers// Computes value of first fibonacci // numbers and stores the even-indexed sumfunction calculateEvenSum($n){ if ($n <= 0) return 0; $fibo[2 * $n + 1] = array(); $fibo[0] = 0; $fibo[1] = 1; // Initialize result $sum = 0; // Add remaining terms for ($i = 2; $i <= 2 * $n; $i++) { $fibo[$i] = $fibo[$i - 1] + $fibo[$i - 2]; // For even indices if ($i % 2 == 0) $sum += $fibo[$i]; } // Return the alternating sum return $sum;}// Driver Code// Get n$n = 8;// Find the even-indiced sumecho "Even indexed Fibonacci Sum upto " . $n . " terms: " . calculateEvenSum($n) . "\n";// This code is contributed // by Akanksha Rai(Abby_akku)?> |
Output
Even indexed Fibonacci Sum upto 8 terms: 1596
Time Complexity: O(n)
Auxiliary Space: O(n)
Method-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 .
So in order to find the required sum, the task is to find only F2n+1 which requires O(log n) time.( Refer to method 5 or method 6 in this article.
Below is the implementation of the above approach:
C++
// C++ Program to find even indexed Fibonacci Sum in// O(Log n) time.#include <bits/stdc++.h>using namespace std;const int MAX = 1000;// Create an array for memoizationint f[MAX] = { 0 };// Returns n'th Fibonacci number// using table f[]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]) return f[n]; int k = (n & 1) ? (n + 1) / 2 : n / 2; // Applying above formula [Note value n&1 is 1 // if n is odd, else 0]. f[n] = (n & 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 Sumint calculateEvenSum(int n){ return (fib(2 * n + 1) - 1);}// Driver program to test above functionint main(){ // Get n int n = 8; // Find the alternating sum cout << "Even indexed Fibonacci Sum upto " << n << " terms: " << calculateEvenSum(n) << endl; return 0;} |
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 = 8; // Find the alternating sum System.out.println("Even indexed Fibonacci Sum upto " + n + " terms: " + calculateEvenSum(n)); }}// This code is contributed by Rajput-Ji |
Python3
# Python3 Program to find even indexed # Fibonacci Sum in O(Log n) time.MAX = 1000;# Create an array for memoizationf = [0] * MAX;# Returns n'th Fibonacci number# using table f[]def fib(n): # Base cases if (n == 0): return 0; if (n == 1 or n == 2): f[n] = 1; return f[n]; # If fib(n) is already computed if (f[n]): return f[n]; k = (n + 1) // 2 if (n % 2 == 1) else n // 2; # Applying above formula [Note value n&1 is 1 # if n is odd, else 0]. f[n] = (fib(k) * fib(k) + fib(k - 1) * fib(k - 1)) \ if (n % 2 == 1) else (2 * fib(k - 1) + fib(k)) * fib(k); return f[n];# Computes value of even-indexed Fibonacci Sumdef calculateEvenSum(n): return (fib(2 * n + 1) - 1);# Driver Codeif __name__ == '__main__': # Get n n = 8; # Find the alternating sum print("Even indexed Fibonacci Sum upto", n, "terms:", calculateEvenSum(n));# This code is contributed by PrinciRaj1992 |
C#
// C# Program to find even indexed Fibonacci Sum in // O(Log n) time. using System;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 code public static void Main() { // Get n int n = 8; // Find the alternating sum Console.WriteLine("Even indexed Fibonacci Sum upto " + n + " terms: " + calculateEvenSum(n)); }}//This code is contributed by 29AjayKumar |
Javascript
<script>// javascript Program to find even indexed Fibonacci Sum in // O(Log n) time. var MAX = 1000; // Create an array for memoization var f = Array(MAX).fill(0); // Returns n'th Fibonacci number // using table f function fib(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]; } var 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 function calculateEvenSum(n) { return (fib(2 * n + 1) - 1); } // Driver program to test above function // Get n var n = 8; // Find the alternating sum document.write("Even indexed Fibonacci Sum upto " + n + " terms: " + calculateEvenSum(n));// This code is contributed by todaysgaurav</script> |
Output
Even indexed Fibonacci Sum upto 8 terms: 1596
Time Complexity: O(logn)
Auxiliary Space: O(logn)
Another approach: Space optimized O(1)
In Method 1 we the current value fibo[i] is only depend upon the previous 2 values i.e. fibo[i-1] and fibo[i-2]. So to optimize the space we can keep track of previous and current values by the help of three variables prev1, prev2 and curr which will reduce the space complexity from O(N) to O(1).
Implementation Steps:
- Create 2 variables prev1 and prev2 to keep track of previous values of fibo.
- Initialize base case prev1 = prev2 = 1.
- Create a variable curr to store current value.
- Create a variable sum used to store the sum of even-indexed sum.
- Iterate over subproblem using loop and update curr.
- After every iteration update prev1 and prev2 for further iterations.
- At last return and print sum.
Implementation:
C++
// C++ Program to find sum// of even-indiced Fibonacci numbers#include <bits/stdc++.h>using namespace std;// Computes value of first fibonacci numbers// and stores the even-indexed sumint calculateEvenSum(int n){ if (n <= 0) return 0; int prev1=0 , prev2=1 ; int curr; // Initialize result int sum = 0; // Add remaining terms for (int i = 2; i <= 2 * n; i++) { curr = prev2 + prev1; // For even indices if (i % 2 == 0) sum += curr; // assigning values to iterate further prev1 = prev2; prev2 = curr; } // Return the alternating sum return sum;}// Driver program to test above functionint main(){ // Get n int n = 8; // Find the even-indiced sum cout << "Even indexed Fibonacci Sum upto " << n << " terms: " << calculateEvenSum(n) << endl; return 0;} |
Java
import java.util.*;public class GFG { // Computes value of first fibonacci numbers and stores // the even-indexed sum static int calculateEvenSum(int n) { if (n <= 0) return 0; int prev1 = 0, prev2 = 1; int curr; // Initialize result int sum = 0; // Add remaining terms for (int i = 2; i <= 2 * n; i++) { curr = prev2 + prev1; // For even indices if (i % 2 == 0) sum += curr; // assigning values to iterate further prev1 = prev2; prev2 = curr; } // Return the alternating sum return sum; } // Driver program to test above function public static void main(String[] args) { // Get n int n = 8; // Find the even-indiced sum System.out.println( "Even indexed Fibonacci Sum upto " + n + " terms: " + calculateEvenSum(n)); }} |
Python
# Python3 Program to find sum# of even-indiced Fibonacci numbersdef calculate_even_sum(n): if n <= 0: return 0 prev1, prev2 = 0, 1 curr = 0 even_sum = 0 # Add remaining terms for i in range(2, 2 * n + 1): curr = prev2 + prev1 # For even indices if i % 2 == 0: even_sum += curr # Assigning values to iterate further prev1 = prev2 prev2 = curr # Return the alternating sum return even_sum# Driver program to test above functionif __name__ == "__main__": # Get n n = 8 # Find the even-indexed sum print("Even indexed Fibonacci Sum upto {} terms: {}".format( n, calculate_even_sum(n))) |
C#
// C# Program to find sum// of even-indiced Fibonacci numbersusing System;class GFG { static int CalculateEvenSum(int n) { if (n <= 0) return 0; int prev1 = 0, prev2 = 1; int curr; // Initialize result int sum = 0; // Add remaining terms for (int i = 2; i <= 2 * n; i++) { curr = prev2 + prev1; // For even indices if (i % 2 == 0) sum += curr; // Assigning values to iterate further prev1 = prev2; prev2 = curr; } // Return the alternating sum return sum; } static void Main(string[] args) { // Get n int n = 8; // Find the even-indexed sum Console.WriteLine( "Even indexed Fibonacci Sum up to " + n + " terms: " + CalculateEvenSum(n)); }} |
Javascript
function GFG(n) { if (n <= 0) return 0; let prev1 = 0, prev2 = 1; let curr; // Initialize result let sum = 0; // Add remaining terms for (let i = 2; i <= 2 * n; i++) { curr = prev2 + prev1; // For even indices if (i % 2 === 0) sum += curr; // assigning values to iterate further prev1 = prev2; prev2 = curr; } // Return the alternating sum return sum;}// Driver program to test // above function Get nlet n = 8;// Find the even-indiced sumconsole.log("Even indexed Fibonacci Sum upto " + n + " terms: " + GFG(n)); |
Output
Even indexed Fibonacci Sum upto 8 terms: 1596
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
