Skip to main content

Sum of n Fibonacci number in constant time

The problem involves finding the sum of the first n Fibonacci numbers in constant time, meaning the time complexity should not increase with n. Fibonacci numbers are a sequence of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. The challenge here is to find a formula or approach that can calculate the sum without iterating through all n numbers.

Problem Statement

Given an integer n, the task is to find the sum of the first n Fibonacci numbers in constant time.

Example

Let's consider n = 7 as an example. The Fibonacci sequence starts with 0 and 1, and the next numbers are obtained by adding the previous two numbers:

Fibonacci sequence: [0, 1, 1, 2, 3, 5, 8, ...]

The sum of the first 7 Fibonacci numbers is 0 + 1 + 1 + 2 + 3 + 5 + 8 = 20.

Idea to Solve

The idea to solve this problem involves using the mathematical properties of the Fibonacci sequence. A formula known as Binet's formula provides a way to directly calculate the n-th Fibonacci number using the golden ratio and its conjugate. By using this formula, we can derive a formula for the sum of the first n Fibonacci numbers.

Pseudocode

function sumFibonacciNo(n)
    if n > 0
        golden_ratio = (1 + sqrt(5)) / 2
        sum = round((pow(golden_ratio, n + 1) - (-1 / golden_ratio^n + 1)) / sqrt(5))
        print "Sum of", n, "Fibonacci numbers is", sum
    else
        print "Invalid value", n

Algorithm Explanation

  1. Check if n is greater than 0.
  2. Calculate the golden ratio using the formula (1 + sqrt(5)) / 2.
  3. Use Binet's formula to calculate the sum of the first n Fibonacci numbers:
    • sum = round((pow(golden_ratio, n + 1) - (-1 / golden_ratio^n + 1)) / sqrt(5))
  4. Print the result.

Solution

/*
    C program for
    Sum of n Fibonacci number in constant time
*/
#include <stdio.h>
#include <math.h>

void sumFibonacciNo(int n)
{
	if (n > 0)
	{
		long long int sum = round(pow((sqrt(5) + 1) / 2.0, n + 1) / sqrt(5));
		// Display calculated result
		printf("\n Sum of %d fibonacci number is %lld", n, sum - 1);
	}
	else
	{
		printf("\n Invalid %d value", n);
	}
}
int main(int argc, char const *argv[])
{
	// Fibonacci sequence 
  	// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
	/*
	   Test A
	   n = 7
	   0 + 1 + 1 + 2 + 3 + 5 + 8
       ----------------------------------------
       20
	*/
	sumFibonacciNo(7);
	/*
	   Test B
	   n = 10
	   0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 
       -----------------------------------------
       88
	*/
	sumFibonacciNo(10);
	return 0;
}

Output

 Sum of 7 fibonacci number is 20
 Sum of 10 fibonacci number is 88
/*
    Java program for
    Sum of n Fibonacci number in constant time
*/
public class FibonacciSeries
{
	public void sumFibonacciNo(int n)
	{
		if (n > 0)
		{
			long sum = Math.round(
              Math.pow((Math.sqrt(5) + 1) / 2.0, n + 1) / 
              Math.sqrt(5));
			// Display calculated result
			System.out.print("\n Sum of " + 
                             n + " fibonacci number is " + (sum - 1));
		}
		else
		{
			System.out.print("\n Invalid " + n + " value");
		}
	}
	public static void main(String[] args)
	{
		FibonacciSeries task = new FibonacciSeries();
		// Fibonacci sequence 
		// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
		/*
		   Test A
		   n = 7
		   0 + 1 + 1 + 2 + 3 + 5 + 8
		   ----------------------------------------
		   20
		*/
		task.sumFibonacciNo(7);
		/*
		   Test B
		   n = 10
		   0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 
		   -----------------------------------------
		   88
		*/
		task.sumFibonacciNo(10);
	}
}

Output

 Sum of 7 fibonacci number is 20
 Sum of 10 fibonacci number is 88
// Include header file
#include <iostream>

#include <math.h>

using namespace std;
/*
    C++ program for
    Sum of n Fibonacci number in constant time
*/
class FibonacciSeries
{
	public: void sumFibonacciNo(int n)
	{
		if (n > 0)
		{
			long sum = round(
              pow((sqrt(5) + 1) / 2.0, n + 1) / sqrt(5)
            );
			// Display calculated result
			cout << "\n Sum of " << n 
                 << " fibonacci number is " << (sum - 1);
		}
		else
		{
			cout << "\n Invalid " << n << " value";
		}
	}
};
int main()
{
	FibonacciSeries *task = new FibonacciSeries();
	// Fibonacci sequence
	// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
	/*
	   Test A
	   n = 7
	   0 + 1 + 1 + 2 + 3 + 5 + 8
	   ----------------------------------------
	   20
	*/
	task->sumFibonacciNo(7);
	/*
	   Test B
	   n = 10
	   0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 
	   -----------------------------------------
	   88
	*/
	task->sumFibonacciNo(10);
	return 0;
}

Output

 Sum of 7 fibonacci number is 20
 Sum of 10 fibonacci number is 88
// Include namespace system
using System;
/*
    Csharp program for
    Sum of n Fibonacci number in constant time
*/
public class FibonacciSeries
{
	public void sumFibonacciNo(int n)
	{
		if (n > 0)
		{
			double sum = Math.Round(
              Math.Pow((Math.Sqrt(5) + 1) / 2.0, n + 1) / Math.Sqrt(5)
            );
			// Display calculated result
			Console.Write("\n Sum of " + 
                          n + " fibonacci number is " + (sum - 1));
		}
		else
		{
			Console.Write("\n Invalid " + n + " value");
		}
	}
	public static void Main(String[] args)
	{
		FibonacciSeries task = new FibonacciSeries();
		// Fibonacci sequence
		// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
		/*
		   Test A
		   n = 7
		   0 + 1 + 1 + 2 + 3 + 5 + 8
		   ----------------------------------------
		   20
		*/
		task.sumFibonacciNo(7);
		/*
		   Test B
		   n = 10
		   0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 
		   -----------------------------------------
		   88
		*/
		task.sumFibonacciNo(10);
	}
}

Output

 Sum of 7 fibonacci number is 20
 Sum of 10 fibonacci number is 88
package main
import "math"
import "fmt"
/*
    Go program for
    Sum of n Fibonacci number in constant time
*/

func sumFibonacciNo(n int) {
	if n > 0 {
		var sum  = math.Round(math.Pow((math.Sqrt(5.0) + 1) / 2.0, 
			float64(n + 1)) / math.Sqrt(5.0))
		// Display calculated result
		fmt.Print("\n Sum of ", n, " fibonacci number is ", (sum - 1))
	} else {
		fmt.Print("\n Invalid ", n, " value")
	}
}
func main() {
	// Fibonacci sequence
	// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
	/*
	   Test A
	   n = 7
	   0 + 1 + 1 + 2 + 3 + 5 + 8
	   ----------------------------------------
	   20
	*/
	sumFibonacciNo(7)
	/*
	   Test B
	   n = 10
	   0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 
	   -----------------------------------------
	   88
	*/
	sumFibonacciNo(10)
}

Output

 Sum of 7 fibonacci number is 20
 Sum of 10 fibonacci number is 88
<?php
/*
    Php program for
    Sum of n Fibonacci number in constant time
*/
class FibonacciSeries
{
	public	function sumFibonacciNo($n)
	{
		if ($n > 0)
		{
			$sum = round(pow((sqrt(5) + 1) / 2.0, $n + 1) / sqrt(5));
			// Display calculated result
			echo("\n Sum of ".$n.
				" fibonacci number is ".($sum - 1));
		}
		else
		{
			echo("\n Invalid ".$n." value");
		}
	}
}

function main()
{
	$task = new FibonacciSeries();
	// Fibonacci sequence
	// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
	/*
	   Test A
	   n = 7
	   0 + 1 + 1 + 2 + 3 + 5 + 8
	   ----------------------------------------
	   20
	*/
	$task->sumFibonacciNo(7);
	/*
	   Test B
	   n = 10
	   0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 
	   -----------------------------------------
	   88
	*/
	$task->sumFibonacciNo(10);
}
main();

Output

 Sum of 7 fibonacci number is 20
 Sum of 10 fibonacci number is 88
/*
    Node JS program for
    Sum of n Fibonacci number in constant time
*/
class FibonacciSeries
{
	sumFibonacciNo(n)
	{
		if (n > 0)
		{
			var sum = Math.round(
              Math.pow((Math.sqrt(5) + 1) / 2.0, n + 1) / Math.sqrt(5)
            );
			// Display calculated result
			process.stdout.write("\n Sum of " + 
                                 n + " fibonacci number is " + (sum - 1));
		}
		else
		{
			process.stdout.write("\n Invalid " + n + " value");
		}
	}
}

function main()
{
	var task = new FibonacciSeries();
	// Fibonacci sequence
	// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
	/*
	   Test A
	   n = 7
	   0 + 1 + 1 + 2 + 3 + 5 + 8
	   ----------------------------------------
	   20
	*/
	task.sumFibonacciNo(7);
	/*
	   Test B
	   n = 10
	   0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 
	   -----------------------------------------
	   88
	*/
	task.sumFibonacciNo(10);
}
main();

Output

 Sum of 7 fibonacci number is 20
 Sum of 10 fibonacci number is 88
import math
#    Python 3 program for
#    Sum of n Fibonacci number in constant time
class FibonacciSeries :
	def sumFibonacciNo(self, n) :
		if (n > 0) :
			sum = round(
              (((math.sqrt(5) + 1) / 2.0) ** (n + 1)) / math.sqrt(5)
            )
			#  Display calculated result
			print("\n Sum of", n ,"fibonacci number is ", (sum - 1), end = "")
		else :
			print("\n Invalid ", n ," value", end = "")
		
	

def main() :
	task = FibonacciSeries()
	#  Fibonacci sequence
	#  [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
	#   Test A
	#   n = 7
	#   0 + 1 + 1 + 2 + 3 + 5 + 8
	#   ----------------------------------------
	#   20
	task.sumFibonacciNo(7)
	#   Test B
	#   n = 10
	#   0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 
	#   -----------------------------------------
	#   88
	task.sumFibonacciNo(10)

if __name__ == "__main__": main()

Output

 Sum of 7 fibonacci number is  20
 Sum of 10 fibonacci number is  88
#    Ruby program for
#    Sum of n Fibonacci number in constant time
class FibonacciSeries 
	def sumFibonacciNo(n) 
		if (n > 0) 
			sum = (
              (((Math.sqrt(5) + 1) / 2.0) ** (n + 1)) / Math.sqrt(5)
            ).round
			#  Display calculated result
			print("\n Sum of ", n ," fibonacci number is ", (sum - 1))
		else
 
			print("\n Invalid ", n ," value")
		end

	end

end

def main() 
	task = FibonacciSeries.new()
	#  Fibonacci sequence
	#  [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
	#   Test A
	#   n = 7
	#   0 + 1 + 1 + 2 + 3 + 5 + 8
	#   ----------------------------------------
	#   20
	task.sumFibonacciNo(7)
	#   Test B
	#   n = 10
	#   0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 
	#   -----------------------------------------
	#   88
	task.sumFibonacciNo(10)
end

main()

Output

 Sum of 7 fibonacci number is 20
 Sum of 10 fibonacci number is 88
/*
    Scala program for
    Sum of n Fibonacci number in constant time
*/
class FibonacciSeries()
{
	def sumFibonacciNo(n: Int): Unit = {
		if (n > 0)
		{
			var sum: Long = Math.round(
              Math.pow((scala.math.sqrt(5) + 1) / 2.0, n + 1) /
              scala.math.sqrt(5)
            );
			// Display calculated result
			print("\n Sum of " + n + " fibonacci number is " + (sum - 1));
		}
		else
		{
			print("\n Invalid " + n + " value");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: FibonacciSeries = new FibonacciSeries();
		// Fibonacci sequence
		// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
		/*
		   Test A
		   n = 7
		   0 + 1 + 1 + 2 + 3 + 5 + 8
		   ----------------------------------------
		   20
		*/
		task.sumFibonacciNo(7);
		/*
		   Test B
		   n = 10
		   0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 
		   -----------------------------------------
		   88
		*/
		task.sumFibonacciNo(10);
	}
}

Output

 Sum of 7 fibonacci number is 20
 Sum of 10 fibonacci number is 88
import Foundation;
/*
    Swift 4 program for
    Sum of n Fibonacci number in constant time
*/
class FibonacciSeries
{
	func sumFibonacciNo(_ n: Int)
	{
		if (n > 0)
		{
			let sum = 
              round(
                pow(((5).squareRoot() + 1) / 2.0, Double(n + 1)) /
                (5).squareRoot()
              );
			// Display calculated result
			print("\n Sum of", 
                  n ,"fibonacci number is", 
                  (sum - 1), terminator: "");
		}
		else
		{
			print("\n Invalid ", n ," value", terminator: "");
		}
	}
}
func main()
{
	let task: FibonacciSeries = FibonacciSeries();
	// Fibonacci sequence
	// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
	/*
	   Test A
	   n = 7
	   0 + 1 + 1 + 2 + 3 + 5 + 8
	   ----------------------------------------
	   20
	*/
	task.sumFibonacciNo(7);
	/*
	   Test B
	   n = 10
	   0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 
	   -----------------------------------------
	   88
	*/
	task.sumFibonacciNo(10);
}
main();

Output

 Sum of 7 fibonacci number is 20.0
 Sum of 10 fibonacci number is 88.0
/*
    Kotlin program for
    Sum of n Fibonacci number in constant time
*/
class FibonacciSeries
{
	fun sumFibonacciNo(n: Int): Unit
	{
		if (n > 0)
		{
			val sum = Math.round(
              Math.pow(
                (Math.sqrt(5.0) + 1) / 2.0, (n + 1).toDouble()) / 
              Math.sqrt(5.0)
            );
			// Display calculated result
			print("\n Sum of " + n + " fibonacci number is " + (sum - 1));
		}
		else
		{
			print("\n Invalid " + n + " value");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: FibonacciSeries = FibonacciSeries();
	// Fibonacci sequence
	// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
	/*
	   Test A
	   n = 7
	   0 + 1 + 1 + 2 + 3 + 5 + 8
	   ----------------------------------------
	   20
	*/
	task.sumFibonacciNo(7);
	/*
	   Test B
	   n = 10
	   0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 
	   -----------------------------------------
	   88
	*/
	task.sumFibonacciNo(10);
}

Output

 Sum of 7 fibonacci number is 20
 Sum of 10 fibonacci number is 88

Time Complexity

The time complexity of this algorithm is constant, O(1), as it involves only a few mathematical calculations that do not depend on the input size. The space complexity is also constant, as it uses a fixed number of variables.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment