Leonardo Number

The Leonardo numbers are a sequence of numbers given by the recurrence:

The first few Leonardo Numbers are 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, ···

The Leonardo numbers are related to the Fibonacci numbers by below relation:

L(n)=2F(n+1)-1, n\geq 0

Given a number n, find n-th Leonardo number.

Input : n = 0
Output : 1

Input : n = 3
Output : 5

simple solution is to recursively compute values.

// A simple recursive program to find n-th
// leonardo number.
#include <iostream>
using namespace std;
int leonardo(int n)
{
    if (n == 0 || n == 1)
        return 1;
    return leonardo(n - 1) + leonardo(n - 2) + 1;
}
int main()
{
    cout << leonardo(3);
    return 0;
}

Output:

5

Time Complexity : Exponential

better solution is to use dynamic programming.

// A simple recursive program to find n-th
// leonardo number.
#include <iostream>
using namespace std;
int leonardo(int n)
{
    int dp[n + 1];
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2] + 1;
    return dp[n];
}
int main()
{
    cout << leonardo(3);
    return 0;
}

Output:

5

Time Complexity : O(n)

The best solution is to use relation with Fibonacci Numbers. We can find n-th Fibonacci number in O(Log n) time .

// A O(Log n) program to find n-th Leonardo
// number.
#include <iostream>
using namespace std;
/* Helper function that multiplies 2 matrices
   F and M of size 2*2, and puts the
   multiplication result back to F[][] */
void multiply(int F[2][2], int M[2][2])
{
    int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}
void power(int F[2][2], int n)
{
    int i;
    int M[2][2] = { { 1, 1 }, { 1, 0 } };
    // n - 1 times multiply the matrix
    // to {{1, 0}, {0, 1}}
    for (i = 2; i <= n; i++)
        multiply(F, M);
}
int fib(int n)
{
    int F[2][2] = { { 1, 1 }, { 1, 0 } };
    if (n == 0)
        return 0;
    power(F, n - 1);
    return F[0][0];
}
int leonardo(int n)
{
    if (n == 0 || n == 1)
        return 1;
    return 2 * fib(n + 1) - 1;
}
int main()
{
    cout << leonardo(3);
    return 0;
}

Output:

5

Time Complexity : O(Log n)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar