Fibonacci Sum in Java
In this article, we will learn how to calculate the Fibonacci series sum up to a given number. A sequence of numbers known as the Fibonacci series, Fibonacci sum, or Fibonacci sequence is composed of several consecutive numbers that add up to a total of two or more previous numbers. In the Fibonacci series, the first two integers are 0 and 1. The value of f0 + f1 + f2 +... + fn, where fi denotes the i'th Fibonacci number, will be found for a given positive number, num.
Note: A Fibonacci series consists of the first two numbers, 0 and 1, and all other numbers that follow are the sum of the two numbers that came before them. For instance, 0, 1, 1, 2, 3, 5...
Example 1:
Input:
int num = 3
Output:
The Fibonacci sum of the number 3 is 4.
Explanation:
The given number is 3, so the previous sum of the consecutive numbers up to sum 3 is 0 + 1 + 1 + 2, and after performing the sum, it gives 4. Hence, the output is printed as 4.
Example 2:
Input:
int num = 5
Output:
The Fibonacci sum of the number 5 is 12.
Explanation:
The given number is 5, so the previous consecutive numbers up to sum 5 are 0 + 1 + 1 + 2 + 3 + 5, and after performing the sum, it gives 12. Hence, the output is printed as 12.
Approach: Brute Force
The Brute Force method is really easy to understand such that locate all of the Fibonacci numbers up to f(n) and then sum them.
Implementation:
FileName: FibSumBruteForce.java
import java.io.*;
import java.util.*;
public class FibSumBruteForce
{
static int Sum(int num)
{
if (num <= 0)
return 0;
int fib[]=new int[num+1];
fib[0] = 0;
fib[1] = 1;
// Initialization of the result
int sum = fib[0] + fib[1];
// Performing the sum of remaining terms
for (int i=2; i<=num; i++)
{
fib[i] = fib[i-1]+fib[i-2];
sum += fib[i];
}
return sum;
}
public static void main(String args[])
{
int num = 5;
System.out.println("The Fibonacci sum of the" + " numbers is : "+ Sum(num));
}
}
Output:
The Fibonacci sum of the numbers is : 12
Complexity Analysis:
The time complexity for the above program is O(N), and the space complexity is given by O(N).
Approach: Without Using Extra Space
In this method, three variables are declared such that two variables have a value equal to '0' (a=0, b=0) and a current variable to store the Fibonacci sum consecutively. The loop is repeated until it is the given input number.
Implementation:
FileName: FibSumWithoutExtraSpace.java
import java.io.*;
import java.util.*;
public class FibSumWithoutExtraSpace
{
public static void main(String args[])
{
int num = 5, a = 0, b = 0, count = 1;
if (num <= 0)
count = 0;
int current = 1;
for(int i = 1; i < num; i++)
{
a = b;
b = current;
current = a+b;
count += current;
}
System.out.println("The Fibonacci sum of the" + " numbers is : " + count);
}
}
Output:
The Fibonacci sum of the numbers is : 12
Complexity Analysis:
The time complexity is O(N), and the space complexity for the above program is O(1).
Approach: Using Recursion
The objective is to establish a relationship between the nth Fibonacci number and the sum of all Fibonacci numbers.
- The symbol F(i) denotes the i-th Fibonacci number.
- The sum of Fibonacci numbers up to F(i) is denoted by S(i).
The equation F(n+1) = F(n) + F(n-1) can be rewritten as follows.
F(n-1) = F(n+1) - F(n)
In a similar way,
F(n-2) = F(n) - F(n-1)
. . .
. . .
. . .
F(0) = F(2) - F(1)
-------------------------------
When we add up all the equations, we get on the left side:
F(0) + F(1) + … F(n-1) which is S(n-1).
Hence,
S(n-1) = F(n+1) – F(1)
S(n-1) = F(n+1) – 1
S(n) = F(n+2) – 1 —(1)
S(n) can be found by simply computing the (n+2)'th Fibonacci number and subtracting 1 from the result.
Implementation:
FileName: FibSumTimeComplexity.java
import java.util.*;
import java.io.*;
public class FibSumTimeComplexity
{
static int MAX = 1000;
// Construct an array for memoization
static int []f = new int[MAX];
// Utilising table f[], returns then'th Fibonacci number.
static int fibon(int num)
{
// Base cases
if (num == 0)
return 0;
if (num == 1 || num == 2)
return (f[num] = 1);
// If fibon(num) has previously been calculated
if (f[num]>0)
return f[num];
int i = ((num & 1)>0)? (num+1)/2 : num/2;
// Using the formula above
// [Note that if n is odd, value n&1 is 1; else, 0].
f[num] = (num & 1)>0? (fibon(i)*fibon(i) + fibon(i-1)*fibon(i-1))
: (2*fibon(i-1) + fibon(i))*fibon(i);
return f[num];
}
// Determines the initial Fibonacci number's value.
static int Sum(int num)
{
return fibon(num + 2) - 1;
}
public static void main(String[] args)
{
int num = 5;
System.out.print("The Fibonacci sum of the" + " numbers is : " + Sum(num));
}
}
Output:
The Fibonacci sum of the numbers is : 12
Complexity Analysis:
The time complexity is O(N), and the space complexity for the above program is O(1).