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
- Check if n is greater than 0.
- Calculate the golden ratio using the formula
(1 + sqrt(5)) / 2
. - 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))
- 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.
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