# 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:

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