Sum of squares of Fibonacci Numbers
The given problem is to find the sum of the squares of the first 'n' Fibonacci numbers. Fibonacci numbers are a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1. The Fibonacci sequence begins with 0 and 1, and each subsequent number is the sum of the two previous numbers.
Problem Statement
We are given an integer 'n' representing the number of Fibonacci numbers to consider. The task is to calculate the sum of the squares of the first 'n' Fibonacci numbers.
Explanation with an Example
Let's take a simple example to understand the problem. Consider 'n' is 5.
Fibonacci sequence: [0, 1, 1, 2, 3, ...]
The first five Fibonacci numbers are: 0, 1, 1, 2, and 3.
Now, we need to find the sum of the squares of these five Fibonacci numbers.
Sum of squares: (0)² + (1)² + (1)² + (2)² + (3)² = 0 + 1 + 1 + 4 + 9 = 15
So, the sum of the squares of the first 5 Fibonacci numbers is 15.
Standard Pseudocode
Before diving into the algorithm, let's write the standard pseudocode for the problem:
function sumFibonacciSquares(n)
sum = 0
if n > 1
create auxiliary array with size n
auxiliary[0] = 0
auxiliary[1] = 1
for i from 0 to n-1
if i > 1
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1]
sum += (auxiliary[i] * auxiliary[i])
print "Sum of", n, "fibonacci square number is", sum
Algorithm Explanation
- Initialize a variable
sumto keep track of the sum of squares of Fibonacci numbers. Set it to 0 initially. - Check if 'n' is greater than 1. If it is not, then there's no need to calculate anything, so we can return.
- Create an auxiliary array of integers with a size of 'n' to store the Fibonacci sequence.
- Set the first two elements of the auxiliary array to 0 and 1, respectively, as these are the first two Fibonacci numbers.
- Use a loop to calculate the next Fibonacci numbers up to the 'n'th number and store them in the auxiliary array.
- During each iteration, calculate the square of the current Fibonacci number and add it to the
sum. - Once the loop is completed, the
sumwill contain the sum of the squares of the first 'n' Fibonacci numbers. - Print the value of
sumas the final output.
Code Solution
Here given code implementation process.
/*
C program for
Sum of squares of Fibonacci Numbers
*/
#include <stdio.h>
void sumFibonacciSquares(int n)
{
long long int sum = 0;
if (n > 1)
{
// Create auxiliary space
int auxiliary[n];
// Set initial sequence
auxiliary[0] = 0;
auxiliary[1] = 1;
// Calculate the sum of n fibonacci numbers
for (int i = 0; i < n; ++i)
{
if (i > 1)
{
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
}
// sum squares of fibonacci number
sum += (auxiliary[i] *auxiliary[i]);
}
}
printf("\n Sum of %d fibonacci square number is %lld", n, sum);
}
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 = 5
(0)² + (1)² + (1)² + (2)² + (3)² = 15
*/
sumFibonacciSquares(5);
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
sumFibonacciSquares(10);
return 0;
}Output
Sum of 5 fibonacci square number is 15
Sum of 10 fibonacci square number is 1870/*
Java program for
Sum of squares of Fibonacci Numbers
*/
public class FibonacciSeries
{
// Here n indicates number of initial Fibonacci series elements
public void sumFibonacciSquares(int n)
{
long sum = 0;
if (n > 1)
{
// Create auxiliary space
int[] auxiliary = new int[n];
// Set initial sequence
auxiliary[0] = 0;
auxiliary[1] = 1;
// Calculate the sum of n fibonacci numbers
for (int i = 0; i < n; ++i)
{
if (i > 1)
{
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
}
// sum squares of fibonacci number
sum += (auxiliary[i] * auxiliary[i]);
}
}
System.out.print("\n Sum of " +
n + " fibonacci square number is " + sum);
}
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 = 5
(0)² + (1)² + (1)² + (2)² + (3)² = 15
*/
task.sumFibonacciSquares(5);
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
task.sumFibonacciSquares(10);
}
}Output
Sum of 5 fibonacci square number is 15
Sum of 10 fibonacci square number is 1870// Include header file
#include <iostream>
using namespace std;
/*
C++ program for
Sum of squares of Fibonacci Numbers
*/
class FibonacciSeries
{
public:
// Here n indicates number of initial Fibonacci series elements
void sumFibonacciSquares(int n)
{
long sum = 0;
if (n > 1)
{
// Create auxiliary space
int auxiliary[n];
// Set initial sequence
auxiliary[0] = 0;
auxiliary[1] = 1;
// Calculate the sum of n fibonacci numbers
for (int i = 0; i < n; ++i)
{
if (i > 1)
{
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
}
// sum squares of fibonacci number
sum += (auxiliary[i] *auxiliary[i]);
}
}
cout << "\n Sum of " << n
<< " fibonacci square number is " << sum;
}
};
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 = 5
(0)² + (1)² + (1)² + (2)² + (3)² = 15
*/
task->sumFibonacciSquares(5);
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
task->sumFibonacciSquares(10);
return 0;
}Output
Sum of 5 fibonacci square number is 15
Sum of 10 fibonacci square number is 1870// Include namespace system
using System;
/*
Csharp program for
Sum of squares of Fibonacci Numbers
*/
public class FibonacciSeries
{
// Here n indicates number of initial Fibonacci series elements
public void sumFibonacciSquares(int n)
{
long sum = 0;
if (n > 1)
{
// Create auxiliary space
int[] auxiliary = new int[n];
// Set initial sequence
auxiliary[0] = 0;
auxiliary[1] = 1;
// Calculate the sum of n fibonacci numbers
for (int i = 0; i < n; ++i)
{
if (i > 1)
{
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
}
// sum squares of fibonacci number
sum += (auxiliary[i] * auxiliary[i]);
}
}
Console.Write("\n Sum of " + n +
" fibonacci square number is " + sum);
}
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 = 5
(0)² + (1)² + (1)² + (2)² + (3)² = 15
*/
task.sumFibonacciSquares(5);
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
task.sumFibonacciSquares(10);
}
}Output
Sum of 5 fibonacci square number is 15
Sum of 10 fibonacci square number is 1870package main
import "fmt"
/*
Go program for
Sum of squares of Fibonacci Numbers
*/
// Here n indicates number of initial Fibonacci series elements
func sumFibonacciSquares(n int) {
var sum int64 = 0
if n > 1 {
// Create auxiliary space
var auxiliary = make([] int, n)
// Set initial sequence
auxiliary[0] = 0
auxiliary[1] = 1
// Calculate the sum of n fibonacci numbers
for i := 0 ; i < n ; i++ {
if i > 1 {
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1]
}
// sum squares of fibonacci number
sum += int64(auxiliary[i] * auxiliary[i])
}
}
fmt.Print("\n Sum of ",
n, " fibonacci square number is ", sum)
}
func main() {
// Fibonacci sequence
// [0 1 1 2 3 5 8 13 21 34 55 89 144 233 377..]
/*
Test A
n = 5
(0)² + (1)² + (1)² + (2)² + (3)² = 15
*/
sumFibonacciSquares(5)
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
sumFibonacciSquares(10)
}Output
Sum of 5 fibonacci square number is 15
Sum of 10 fibonacci square number is 1870<?php
/*
Php program for
Sum of squares of Fibonacci Numbers
*/
class FibonacciSeries
{
// Here n indicates number of initial Fibonacci series elements
public function sumFibonacciSquares($n)
{
$sum = 0;
if ($n > 1)
{
// Create auxiliary space
$auxiliary = array_fill(0, $n, 0);
// Set initial sequence
$auxiliary[0] = 0;
$auxiliary[1] = 1;
// Calculate the sum of n fibonacci numbers
for ($i = 0; $i < $n; ++$i)
{
if ($i > 1)
{
$auxiliary[$i] = $auxiliary[$i - 2] + $auxiliary[$i - 1];
}
// sum squares of fibonacci number
$sum += ($auxiliary[$i] * $auxiliary[$i]);
}
}
echo("\n Sum of ".$n.
" fibonacci square number is ".$sum);
}
}
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 = 5
(0)² + (1)² + (1)² + (2)² + (3)² = 15
*/
$task->sumFibonacciSquares(5);
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
$task->sumFibonacciSquares(10);
}
main();Output
Sum of 5 fibonacci square number is 15
Sum of 10 fibonacci square number is 1870/*
Node JS program for
Sum of squares of Fibonacci Numbers
*/
class FibonacciSeries
{
// Here n indicates number of initial Fibonacci series elements
sumFibonacciSquares(n)
{
var sum = 0;
if (n > 1)
{
// Create auxiliary space
var auxiliary = Array(n).fill(0);
// Set initial sequence
auxiliary[0] = 0;
auxiliary[1] = 1;
// Calculate the sum of n fibonacci numbers
for (var i = 0; i < n; ++i)
{
if (i > 1)
{
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
}
// sum squares of fibonacci number
sum += (auxiliary[i] * auxiliary[i]);
}
}
process.stdout.write("\n Sum of " +
n + " fibonacci square number is " + sum);
}
}
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 = 5
(0)² + (1)² + (1)² + (2)² + (3)² = 15
*/
task.sumFibonacciSquares(5);
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
task.sumFibonacciSquares(10);
}
main();Output
Sum of 5 fibonacci square number is 15
Sum of 10 fibonacci square number is 1870# Python 3 program for
# Sum of squares of Fibonacci Numbers
class FibonacciSeries :
# Here n indicates number of initial Fibonacci series elements
def sumFibonacciSquares(self, n) :
sum = 0
if (n > 1) :
# Create auxiliary space
auxiliary = [0] * (n)
# Set initial sequence
auxiliary[0] = 0
auxiliary[1] = 1
i = 0
# Calculate the sum of n fibonacci numbers
while (i < n) :
if (i > 1) :
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1]
# sum squares of fibonacci number
sum += (auxiliary[i] * auxiliary[i])
i += 1
print("\n Sum of", n ,"fibonacci square number is ",
sum, 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 = 5
# (0)² + (1)² + (1)² + (2)² + (3)² = 15
task.sumFibonacciSquares(5)
# Test B
# n = 10
# (0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
# (8)² + (13)² + (21)² + (34)² = 1870
task.sumFibonacciSquares(10)
if __name__ == "__main__": main()Output
Sum of 5 fibonacci square number is 15
Sum of 10 fibonacci square number is 1870# Ruby program for
# Sum of squares of Fibonacci Numbers
class FibonacciSeries
# Here n indicates number of initial Fibonacci series elements
def sumFibonacciSquares(n)
sum = 0
if (n > 1)
# Create auxiliary space
auxiliary = Array.new(n) {0}
# Set initial sequence
auxiliary[0] = 0
auxiliary[1] = 1
i = 0
# Calculate the sum of n fibonacci numbers
while (i < n)
if (i > 1)
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1]
end
# sum squares of fibonacci number
sum += (auxiliary[i] * auxiliary[i])
i += 1
end
end
print("\n Sum of ", n ," fibonacci square number is ", sum)
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 = 5
# (0)² + (1)² + (1)² + (2)² + (3)² = 15
task.sumFibonacciSquares(5)
# Test B
# n = 10
# (0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
# (8)² + (13)² + (21)² + (34)² = 1870
task.sumFibonacciSquares(10)
end
main()Output
Sum of 5 fibonacci square number is 15
Sum of 10 fibonacci square number is 1870/*
Scala program for
Sum of squares of Fibonacci Numbers
*/
class FibonacciSeries()
{
// Here n indicates number of initial Fibonacci series elements
def sumFibonacciSquares(n: Int): Unit = {
var sum: Long = 0;
if (n > 1)
{
// Create auxiliary space
var auxiliary: Array[Int] = Array.fill[Int](n)(0);
// Set initial sequence
auxiliary(0) = 0;
auxiliary(1) = 1;
var i: Int = 0;
// Calculate the sum of n fibonacci numbers
while (i < n)
{
if (i > 1)
{
auxiliary(i) = auxiliary(i - 2) + auxiliary(i - 1);
}
// sum squares of fibonacci number
sum += (auxiliary(i) * auxiliary(i));
i += 1;
}
}
print("\n Sum of " + n + " fibonacci square number is " + sum);
}
}
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 = 5
(0)² + (1)² + (1)² + (2)² + (3)² = 15
*/
task.sumFibonacciSquares(5);
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
task.sumFibonacciSquares(10);
}
}Output
Sum of 5 fibonacci square number is 15
Sum of 10 fibonacci square number is 1870/*
Swift 4 program for
Sum of squares of Fibonacci Numbers
*/
class FibonacciSeries
{
// Here n indicates number of initial Fibonacci series elements
func sumFibonacciSquares(_ n: Int)
{
var sum: Int = 0;
if (n > 1)
{
// Create auxiliary space
var auxiliary: [Int] = Array(repeating: 0, count: n);
// Set initial sequence
auxiliary[0] = 0;
auxiliary[1] = 1;
var i: Int = 0;
// Calculate the sum of n fibonacci numbers
while (i < n)
{
if (i > 1)
{
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
}
// sum squares of fibonacci number
sum += (auxiliary[i] * auxiliary[i]);
i += 1;
}
}
print("\n Sum of ", n ,
" fibonacci square number is ", sum, 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 = 5
(0)² + (1)² + (1)² + (2)² + (3)² = 15
*/
task.sumFibonacciSquares(5);
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
task.sumFibonacciSquares(10);
}
main();Output
Sum of 5 fibonacci square number is 15
Sum of 10 fibonacci square number is 1870/*
Kotlin program for
Sum of squares of Fibonacci Numbers
*/
class FibonacciSeries
{
// Here n indicates number of initial Fibonacci series elements
fun sumFibonacciSquares(n: Int): Unit
{
var sum: Long = 0;
if (n > 1)
{
// Create auxiliary space
var auxiliary: Array < Int > = Array(n)
{
0
};
// Set initial sequence
auxiliary[1] = 1;
var i: Int = 0;
// Calculate the sum of n fibonacci numbers
while (i < n)
{
if (i > 1)
{
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
}
// sum squares of fibonacci number
sum += (auxiliary[i] * auxiliary[i]);
i += 1;
}
}
print("\n Sum of " + n + " fibonacci square number is " + sum);
}
}
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 = 5
(0)² + (1)² + (1)² + (2)² + (3)² = 15
*/
task.sumFibonacciSquares(5);
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
task.sumFibonacciSquares(10);
}Output
Sum of 5 fibonacci square number is 15
Sum of 10 fibonacci square number is 1870Resultant Output Explanation
Now, let's consider the two test cases mentioned in the code and understand their outputs.
-
Test A: n = 5
The first 5 Fibonacci numbers are [0, 1, 1, 2, 3]. The sum of their squares is:
Sum of squares: (0)² + (1)² + (1)² + (2)² + (3)² = 0 + 1 + 1 + 4 + 9 = 15
So, the output will be: "Sum of 5 fibonacci square number is 15"
-
Test B: n = 10
The first 10 Fibonacci numbers are [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]. The sum of their squares is:
Sum of squares: (0)² + (1)² + (1)² + (2)² + (3)² + (5)² + (8)² + (13)² + (21)² + (34)² = 0 + 1 + 1 + 4 + 9 + 25 + 64 + 169 + 441 + 1156 = 1870
So, the output will be: "Sum of 10 fibonacci square number is 1870"
Time Complexity
Let's analyze the time complexity of the provided code:
- The loop iterates 'n' times to calculate the first 'n' Fibonacci numbers.
- Each Fibonacci number requires O(1) time to calculate since it is the sum of the previous two numbers.
- Therefore, the time complexity of the loop is O(n).
Overall, the time complexity of the code is O(n), which is linear in the input 'n'. This is an efficient solution for calculating the sum of the squares of 'n' Fibonacci numbers.
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