Given a number positive number n, find value of f0 + f1 + f2 + …. + fn where fi indicates i’th Fibonacci number. Remember that f0 = 0, f1 = 1, f2 = 1, f3 = 2, f4 = 3, f5 = 5, …
Examples :
Input : n = 3
Output : 4
Explanation : 0 + 1 + 1 + 2 = 4
Input : n = 4
Output : 7
Explanation : 0 + 1 + 1 + 2 + 3 = 7
Method 1 (O(n))
Brute Force approach is pretty straightforward, find all the Fibonacci numbers till f(n) and then add them up.
C++
#include<bits/stdc++.h>
using namespace std;
int calculateSum( int n)
{
if (n <= 0)
return 0;
int fibo[n+1];
fibo[0] = 0, fibo[1] = 1;
int sum = fibo[0] + fibo[1];
for ( int i=2; i<=n; i++)
{
fibo[i] = fibo[i-1]+fibo[i-2];
sum += fibo[i];
}
return sum;
}
int main()
{
int n = 4;
cout << "Sum of Fibonacci numbers is : "
<< calculateSum(n) << endl;
return 0;
}
|
Java
import java.io.*;
class GFG {
static int calculateSum( int n)
{
if (n <= 0 )
return 0 ;
int fibo[]= new int [n+ 1 ];
fibo[ 0 ] = 0 ; fibo[ 1 ] = 1 ;
int sum = fibo[ 0 ] + fibo[ 1 ];
for ( int i= 2 ; i<=n; i++)
{
fibo[i] = fibo[i- 1 ]+fibo[i- 2 ];
sum += fibo[i];
}
return sum;
}
public static void main(String args[])
{
int n = 4 ;
System.out.println( "Sum of Fibonacci" +
" numbers is : " + calculateSum(n));
}
}
|
Python3
def calculateSum(n) :
if (n < = 0 ) :
return 0
fibo = [ 0 ] * (n + 1 )
fibo[ 1 ] = 1
sm = fibo[ 0 ] + fibo[ 1 ]
for i in range ( 2 ,n + 1 ) :
fibo[i] = fibo[i - 1 ] + fibo[i - 2 ]
sm = sm + fibo[i]
return sm
n = 4
print ( "Sum of Fibonacci numbers is : " ,
calculateSum(n))
|
C#
using System;
class GFG
{
static int calculateSum( int n)
{
if (n <= 0)
return 0;
int []fibo = new int [n + 1];
fibo[0] = 0; fibo[1] = 1;
int sum = fibo[0] + fibo[1];
for ( int i = 2; i <= n; i++)
{
fibo[i] = fibo[i - 1] + fibo[i - 2];
sum += fibo[i];
}
return sum;
}
static void Main()
{
int n = 4;
Console.WriteLine( "Sum of Fibonacci" +
" numbers is : " +
calculateSum(n));
}
}
|
PHP
<?php
function calculateSum( $n )
{
if ( $n <= 0)
return 0;
$fibo [0] = 0;
$fibo [1] = 1;
$sum = $fibo [0] + $fibo [1];
for ( $i = 2; $i <= $n ; $i ++)
{
$fibo [ $i ] = $fibo [ $i - 1] +
$fibo [ $i - 2];
$sum += $fibo [ $i ];
}
return $sum ;
}
$n = 4;
echo "Sum of Fibonacci numbers is : " ,
calculateSum( $n ), "\n" ;
?>
|
Javascript
<script>
function calculateSum(n)
{
let fibo = [];
if (n <= 0)
return 0;
fibo[0] = 0;
fibo[1] = 1;
let sum = fibo[0] + fibo[1];
for (let i = 2; i <= n; i++)
{
fibo[i] = fibo[i - 1] +
fibo[i - 2];
sum += fibo[i];
}
return sum;
}
let n = 4;
document.write(`Sum of Fibonacci numbers is :
${calculateSum(n)} <br>`);
</script>
|
Output
Sum of Fibonacci numbers is : 7
Time Complexity: O(n)
Auxiliary Space: O(n)
Method 2 : Without using extra space
C++
#include <iostream>
using namespace std;
int main() {
int n = 4, a = 0, b = 0, sumf = 1;
if (n<=0)
sumf = 0;
int curr = 1;
for ( int i = 1;i<n;i++){
a = b;
b = curr;
curr = a+b;
sumf += curr;
}
cout<< "The sum of fibonocci numbers is:" <<sumf<<endl;
return 0;
}
|
Java
import java.io.*;
class GFG
{
public static void main(String args[])
{
int n = 4 , a = 0 , b = 0 , sumf = 1 ;
if (n <= 0 )
sumf = 0 ;
int curr = 1 ;
for ( int i = 1 ; i < n; i++){
a = b;
b = curr;
curr = a+b;
sumf += curr;
}
System.out.println( "The sum of fibonocci numbers is:" +sumf);
}
}
|
Python3
n = 4
a = 0
b = 0
sumf = 1
if n< = 0 :
sumf = 0
curr = 1
for i in range ( 1 ,n):
a = b
b = curr
curr = a + b
sumf + = curr
print ( "The sum of fibonocci numbers is:" ,sumf)
|
Javascript
let n = 4, a = 0, b = 0, sumf = 1;
if (n<=0)
sumf = 0;
let curr = 1;
for (let i = 1;i<n;i++){
a = b;
b = curr;
curr = a+b;
sumf += curr;
}
console.log( "The sum of fibonocci numbers is:" +sumf);
|
C#
using System;
using System.Collections.Generic;
class Gfg
{
public static void Main( string [] args)
{
int n = 4, a = 0, b = 0, sumf = 1;
if (n<=0)
sumf = 0;
int curr = 1;
for ( int i = 1;i<n;i++){
a = b;
b = curr;
curr = a+b;
sumf += curr;
}
Console.Write( "The sum of fibonocci numbers is:" +sumf);
}
}
|
Output
The sum of fibonocci numbers is:7
Time Complexity: O(n)
Auxiliary Space: O(1)
Method 3 (O(Log n))
The idea is to find relationship between the sum of Fibonacci numbers and n’th Fibonacci number.
F(i) refers to the i’th Fibonacci number.
S(i) refers to sum of Fibonacci numbers till F(i),
We can rewrite the relation F(n+1) = F(n) + F(n-1) as below
F(n-1) = F(n+1) - F(n)
Similarly,
F(n-2) = F(n) - F(n-1)
. . .
. . .
. . .
F(0) = F(2) - F(1)
-------------------------------
Adding all the equations, on left side, we have
F(0) + F(1) + … F(n-1) which is S(n-1).
Therefore,
S(n-1) = F(n+1) – F(1)
S(n-1) = F(n+1) – 1
S(n) = F(n+2) – 1 —-(1)
In order to find S(n), simply calculate the (n+2)’th Fibonacci number and subtract 1 from the result.
F(n) can be evaluated in O(log n) time using either method 5 or method 6 in this article (Refer to methods 5 and 6).
Below is the implementation based on method 6 of this
C++
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
int f[MAX] = {0};
int fib( int n)
{
if (n == 0)
return 0;
if (n == 1 || n == 2)
return (f[n] = 1);
if (f[n])
return f[n];
int k = (n & 1)? (n+1)/2 : n/2;
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];
}
int calculateSum( int n)
{
return fib(n+2) - 1;
}
int main()
{
int n = 4;
cout << "Sum of Fibonacci numbers is : "
<< calculateSum(n) << endl;
return 0;
}
|
Java
import java.util.*;
class GFG{
static int MAX = 1000 ;
static int []f = new int [MAX];
static int fib( int n)
{
if (n == 0 )
return 0 ;
if (n == 1 || n == 2 )
return (f[n] = 1 );
if (f[n]> 0 )
return f[n];
int k = ((n & 1 )> 0 )? (n+ 1 )/ 2 : n/ 2 ;
f[n] = (n & 1 )> 0 ? (fib(k)*fib(k) + fib(k- 1 )*fib(k- 1 ))
: ( 2 *fib(k- 1 ) + fib(k))*fib(k);
return f[n];
}
static int calculateSum( int n)
{
return fib(n+ 2 ) - 1 ;
}
public static void main(String[] args)
{
int n = 4 ;
System.out.print( "Sum of Fibonacci numbers is : "
+ calculateSum(n) + "\n" );
}
}
|
Python3
MAX = 1000
f = [ 0 ] * MAX
def fib(n):
n = int (n)
if (n = = 0 ):
return 0
if (n = = 1 or n = = 2 ):
return ( 1 )
if (f[n] = = True ):
return f[n]
k = (n + 1 ) / 2 if (n & 1 ) else n / 2
f[n] = (fib(k) * fib(k) + fib(k - 1 ) * fib(k - 1 )) if (n & 1 ) else ( 2 * fib(k - 1 ) + fib(k)) * fib(k)
return f[n]
def calculateSum(n):
return fib(n + 2 ) - 1
n = 4
print ( "Sum of Fibonacci numbers is :" , calculateSum(n))
|
C#
using System;
class GFG {
static int MAX = 1000;
static int []f = new int [MAX];
static int fib( int n)
{
for ( int i = 0;i < MAX;i++)
f[i] = 0;
if (n == 0)
return 0;
if (n == 1 || n == 2)
return (f[n] = 1);
if (f[n] == 1)
return f[n];
int k;
if ((n & 1) == 1)
k = (n + 1) / 2 ;
else
k = n / 2;
if ((n & 1) == 1)
f[n] = (fib(k) * fib(k) + fib(k - 1)
* fib(k - 1));
else
f[n] = (2 * fib(k - 1) + fib(k)) *
fib(k);
return f[n];
}
static int calculateSum( int n)
{
return fib(n + 2) - 1;
}
public static void Main()
{
int n = 4;
Console.Write( "Sum of Fibonacci numbers is : "
+ calculateSum(n));
}
}
|
PHP
<?php
$MAX = 1000;
$f = array_fill (0, $MAX , 0);
function fib( $n )
{
global $f ;
if ( $n == 0)
return 0;
if ( $n == 1 || $n == 2)
return ( $f [ $n ] = 1);
if ( $f [ $n ])
return $f [ $n ];
$k = ( $n & 1) ? ( $n + 1) / 2 : $n / 2;
$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 ];
}
function calculateSum( $n )
{
return fib( $n + 2) - 1;
}
$n = 4;
print ( "Sum of Fibonacci numbers is : " .
calculateSum( $n ));
?>
|
Javascript
<script>
var MAX = 1000;
var f = Array(MAX).fill(0);
function fib(n) {
if (n == 0)
return 0;
if (n == 1 || n == 2)
return (f[n] = 1);
if (f[n] > 0)
return f[n];
var k = ((n & 1) > 0) ? (n + 1) / 2 : n / 2;
f[n] = (n & 1) > 0 ? (fib(k) * fib(k) + fib(k - 1) * fib(k - 1)) : (2 * fib(k - 1) + fib(k)) * fib(k);
return f[n];
}
function calculateSum(n) {
return fib(n + 2) - 1;
}
var n = 4;
document.write( "Sum of Fibonacci numbers is : " + calculateSum(n) + "\n" );
</script>
|
Output
Sum of Fibonacci numbers is : 7
Time Complexity: O(logn)
Auxiliary Space: O(MAX)
This article is contributed by Chirag Agarwal. If you like neveropen and would like to contribute, you can also write an article and mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
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!