Space optimization from O(N)Linear to O(1)Constant
Calculate the nth Fibonacci number:
State: f[i] –> Denotes the ith Fibonacci number.
Transition: f[i] = f[i-1] + f[i-2]
Code:
// C++ program for Fibonacci Series
// using Dynamic Programming
#include <bits/stdc++.h>
using namespace std;
class GFG {
public:
int fib(int n)
{
// Declare an array to store
// Fibonacci numbers.
// 1 extra to handle
// case, n = 0
int f[n + 2];
int i;
// 0th and 1st number of the
// series are 0 and 1
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++) {
// Add the previous 2 numbers
// in the series and store it
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
};
// Driver code
int main()
{
GFG g;
int n = 9;
cout << g.fib(n);
return 0;
}
public class Fibonacci {
public int fib(int n) {
// Declare an array to store Fibonacci numbers.
// 1 extra to handle case, n = 0
int[] f = new int[n + 2];
int i;
// 0th and 1st number of the series are 0 and 1
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++) {
// Add the previous 2 numbers in the series and store it
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
// Driver code
public static void main(String[] args) {
Fibonacci fibonacci = new Fibonacci();
int n = 9;
System.out.println(fibonacci.fib(n));
}
}
using System;
public class Fibonacci
{
public int Fib(int n)
{
// Declare an array to store Fibonacci numbers.
// 1 extra to handle case, n = 0
int[] f = new int[n + 2];
int i;
// 0th and 1st number of the series are 0 and 1
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++)
{
// Add the previous 2 numbers in the series and store it
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
// Driver code
public static void Main(string[] args)
{
Fibonacci fibonacci = new Fibonacci();
int n = 9;
Console.WriteLine(fibonacci.Fib(n));
}
}
class Fibonacci {
fib(n) {
// Declare an array to store Fibonacci numbers.
// 1 extra to handle case, n = 0
const f = new Array(n + 2);
let i;
// 0th and 1st number of the series are 0 and 1
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++) {
// Add the previous 2 numbers in the series and store it
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
}
// Driver code
const fibonacci = new Fibonacci();
const n = 9;
console.log(fibonacci.fib(n));
class GFG:
def fib(self, n):
# Declare a list to store Fibonacci numbers.
# 1 extra to handle the case, n = 0
f = [0] * (n + 2)
# 0th and 1st number of the series are 0 and 1
f[0] = 0
f[1] = 1
for i in range(2, n + 1):
# Add the previous 2 numbers
# in the series and store it
f[i] = f[i - 1] + f[i - 2]
return f[n]
# Driver code
if __name__ == "__main__":
g = GFG()
n = 9
print(g.fib(n))
Output
34
Time Complexity: O(N)
Auxiliary space: O(N)
Steps To Optimise the Space in action for above problem:
- If we observe clearly, To generate the f[i] we need only two previous states that is f[i-1] and f[i-2].
- Store previous two states in prev1 and prev2 and current in curr.
- After calculating the curr, update the prev2 as prev1 and prev1 as curr.
- At the end, result is stored in the prev1.
Space Optimised Code:
// Fibonacci Series using Space Optimized Method
#include <bits/stdc++.h>
using namespace std;
int fib(int n)
{
int prev2 = 0;
if (n == 0)
return prev2;
int prev1 = 1;
int curr;
for (int i = 2; i <= n; i++) {
curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
// Driver code
int main()
{
int n = 9;
cout << fib(n);
return 0;
}
public class FibonacciSeries {
public static int fib(int n) {
int prev2 = 0;
if (n == 0)
return prev2;
int prev1 = 1;
int curr;
for (int i = 2; i <= n; i++) {
curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
public static void main(String[] args) {
int n = 9;
System.out.println(fib(n));
}
}
using System;
class Program {
// Function to calculate the Fibonacci number at index n
static int Fibonacci(int n)
{
int prev2 = 0;
if (n == 0)
return prev2;
int prev1 = 1;
int curr;
for (int i = 2; i <= n; i++) {
curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
// Main method
static void Main(string[] args)
{
int n = 9; // Index of the Fibonacci number to find
Console.WriteLine(Fibonacci(
n)); // Print the Fibonacci number at index n
}
}
// Function to calculate the Fibonacci series using space-optimized method
function fib(n) {
let prev2 = 0; // Initialize the first Fibonacci number (0)
if (n === 0) return prev2; // If n is 0, return the first Fibonacci number
let prev1 = 1; // Initialize the second Fibonacci number (1)
let curr; // Initialize the current Fibonacci number
for (let i = 2; i <= n; i++) { // Loop through from the 3rd Fibonacci number to the nth Fibonacci number
curr = prev1 + prev2; // Calculate the current Fibonacci number by adding the previous two Fibonacci numbers
prev2 = prev1; // Update the previous two Fibonacci numbers for the next iteration
prev1 = curr;
}
return prev1;
}
// Driver code
let n = 9;
console.log(fib(n));
def fib(n):
prev2, prev1 = 0, 1
if n == 0:
return prev2
for i in range(2, n + 1):
curr = prev1 + prev2
prev2, prev1 = prev1, curr
return prev1
# Driver code
if __name__ == "__main__":
n = 9
print(fib(n))
Output
34
Time Complexity: O(N)
Auxillary space: O(1)