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)