Table of Contents

- Introduction
- Questions
- 1. What is the Fibonacci sequence?
- 2. What is the mathematical definition of the Fibonacci sequence?
- 3. What is the Golden Ratio, and how is it related to the Fibonacci sequence?
- 4. What are some real-world applications or phenomena where the Fibonacci sequence is observed?
- 5. What is the time complexity of the naive recursive approach to calculate Fibonacci numbers?
- 6. What is memoization, and how can it be used to optimize the calculation of Fibonacci numbers?
- 7. What is dynamic programming, and how does it relate to the Fibonacci sequence?
- 8. Explain the iterative method to calculate Fibonacci numbers.
- 9. Can Fibonacci numbers be calculated in constant time? If yes, how?
- 10. What is matrix exponentiation, and how can it be used to compute Fibonacci numbers?
- 11. How is the Fibonacci sequence used in sorting algorithms (like heapsort)?
- 12. What are some of the mathematical properties of the Fibonacci sequence?
- 13. How does the Fibonacci sequence relate to the concept of recursion?
- 14. What is a Fibonacci heap in data structures?
- 15. What are Fibonacci retracements, and how are they used in financial markets?
- Coding Questions
- 16. Write a function to generate the nth Fibonacci number using recursion.
- 17. Write a function to generate the nth Fibonacci number using dynamic programming.
- 18. Write a function to generate the nth Fibonacci number using matrix exponentiation.
- 19. Write a function to print the first n Fibonacci numbers.
- 20. Write a function to calculate the sum of the first n Fibonacci numbers.
- 21. Write a program to check if a given number is a Fibonacci number.
- 22. Write a function to find the greatest common divisor (GCD) of two Fibonacci numbers.
- 23. Write a function to compute the nth Fibonacci number modulo m.
- 24. Write a function that returns the index of the first Fibonacci number with n digits.
- 25. Write a function to find the number of ways to represent a number as a sum of Fibonacci numbers.
- 26. Write a function to generate Fibonacci numbers that fit within a given range.
- 27. Write a function to find the minimum number of Fibonacci numbers whose sum is equal to a given number.
- 28. Write a function to find the last digit of the nth Fibonacci number.
- 29. Write a function to find the number of digits in the nth Fibonacci number.
- 30. Write a function to find the Fibonacci series in reverse order.
- MCQ Questions
- 1. What is the Fibonacci series?
- 2. What are the first two numbers in the Fibonacci series?
- 3. What is the next number in the Fibonacci series after 1, 1?
- 4. What is the Fibonacci number after 13?
- 5. What is the value of the 10th Fibonacci number?
- 6. Which approach is commonly used to calculate Fibonacci numbers recursively?
- 7. Which of the following algorithms can efficiently compute the nth Fibonacci number in O(n) time complexity?
- 8. What is the time complexity of the matrix exponentiation algorithm to calculate the nth Fibonacci number?
- 9. Which of the following methods is an efficient approach to calculate Fibonacci numbers without using recursion?
- 10. What is the value of the sum of the first 10 Fibonacci numbers?
- 11. Which of the following series is similar to the Fibonacci series?
- 12. In the Fibonacci series, what is the ratio of consecutive Fibonacci numbers as they approach infinity?
- 13. Which of the following is NOT a property of the Fibonacci series?
- 14 . What is the largest Fibonacci number that can be represented using 32 bits?
- 15. Which of the following algorithms can efficiently calculate the nth Fibonacci number using memoization?
- 16. What is the Fibonacci number before 377?
- 17. What is the Fibonacci number after 6765?
- 18. Which of the following algorithms can calculate the nth Fibonacci number with the lowest time complexity?
- 19. What is the Fibonacci number after 89?
- 20. Which of the following properties is NOT true for the Fibonacci series?

## Introduction

The Fibonacci series is a sequence of numbers in which each number is the sum of the two preceding ones. It starts with 0 and 1, and each subsequent number is the sum of the previous two (0, 1, 1, 2, 3, 5, 8, and so on). In interviews, Fibonacci series questions are often asked to assess a candidate’s problem-solving and programming skills. Candidates may be asked to generate the Fibonacci series up to a given number or to find the nth number in the series. It’s important to understand the recursive nature of the series and be able to implement an efficient algorithm to solve these questions.

## Questions

### 1. What is the Fibonacci sequence?

The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones. It starts with 0 and 1, and then each subsequent number is the sum of the two previous ones. The sequence goes like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on.

### 2. What is the mathematical definition of the Fibonacci sequence?

The mathematical definition of the Fibonacci sequence is given by the following recurrence relation:

F(n) = F(n-1) + F(n-2)

where F(n) is the nth term in the Fibonacci sequence, F(n-1) is the (n-1)th term, and F(n-2) is the (n-2)th term.

For example, let’s calculate the 6th term in the Fibonacci sequence:

F(6) = F(5) + F(4)

= (F(4) + F(3)) + (F(3) + F(2))

= ((F(3) + F(2)) + (F(2) + F(1))) + ((F(2) + F(1)) + F(1))

= (((F(2) + F(1)) + F(1)) + (F(1) + F(0))) + ((F(1) + F(0)) + F(1))

= (((1 + 1) + 1) + (1 + 0)) + ((1 + 0) + 1)

= (3 + 1) + (1 + 1)

= 4 + 2

= 6

So, the 6th term in the Fibonacci sequence is 6.

### 3. What is the Golden Ratio, and how is it related to the Fibonacci sequence?

The Golden Ratio, often denoted by the Greek letter phi (φ), is an irrational number approximately equal to 1.6180339887. It has many interesting mathematical properties and is related to the Fibonacci sequence in the following way:

As the Fibonacci sequence progresses, the ratio of consecutive Fibonacci numbers approaches the Golden Ratio. Specifically, as n approaches infinity, the ratio of F(n) to F(n-1) converges to the Golden Ratio.

Mathematically, this can be expressed as:

lim (n → ∞) F(n)/F(n-1) = φ

Let’s demonstrate this relationship with a C++ code that calculates the first few Fibonacci numbers and their ratios:

```
#include <iostream>
#include <cmath>
using namespace std;
int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int n = 10; // Change this value to calculate more Fibonacci numbers
cout << "Fibonacci sequence up to " << n << " terms:" << endl;
for (int i = 0; i < n; i++) {
cout << fibonacci(i) << " ";
}
cout << endl << "Ratios of consecutive Fibonacci numbers:" << endl;
for (int i = 2; i < n; i++) {
double ratio = static_cast<double>(fibonacci(i)) / fibonacci(i - 1);
cout << ratio << " ";
}
cout << endl;
return 0;
}
```

### 4. What are some real-world applications or phenomena where the Fibonacci sequence is observed?

The Fibonacci sequence appears in various real-world applications and phenomena, some of which include:

**Nature:**The Fibonacci sequence is often found in natural patterns, such as the arrangement of leaves on a stem, the spiral pattern of sunflower seeds, pinecones, and nautilus shells.**Finance:**The Fibonacci sequence is used in financial markets for predicting price movements and analyzing trends. Fibonacci retracements and extensions are commonly used by traders and technical analysts.**Computer Algorithms:**Fibonacci numbers and the Fibonacci sequence are used in various algorithms, such as dynamic programming, matrix exponentiation, and sorting algorithms.**Art and Design:**Artists and designers sometimes use the Fibonacci sequence to create visually appealing compositions and layouts.**Architecture:**Fibonacci numbers have been used in architecture to create harmonious proportions in buildings and structures.

### 5. What is the time complexity of the naive recursive approach to calculate Fibonacci numbers?

The time complexity of the naive recursive approach to calculate Fibonacci numbers is exponential, specifically O(2^n). This is because the recursive function makes redundant and overlapping calls, leading to an inefficient computation of Fibonacci numbers.

Let’s see an example of the naive recursive implementation to calculate the Fibonacci number of a given index:

```
#include <iostream>
using namespace std;
int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int n = 6; // Calculate the 6th Fibonacci number
cout << "Fibonacci number at index " << n << " is: " << fibonacci(n) << endl;
return 0;
}
```

When we calculate the 6th Fibonacci number using this code, the function calls are as follows:

```
fibonacci(6) -> fibonacci(5) + fibonacci(4)
fibonacci(5) -> fibonacci(4) + fibonacci(3)
fibonacci(4) -> fibonacci(3) + fibonacci(2)
fibonacci(3) -> fibonacci(2) + fibonacci(1)
fibonacci(2) -> fibonacci(1) + fibonacci(0)
fibonacci(3) -> fibonacci(2) + fibonacci(1)
```

As we can see, the same Fibonacci numbers are being recalculated multiple times, leading to redundant computations. This inefficiency becomes more pronounced as the value of ‘n’ increases, resulting in exponential time complexity.

### 6. What is memoization, and how can it be used to optimize the calculation of Fibonacci numbers?

Memoization is a technique used to optimize recursive algorithms by storing the results of expensive function calls and returning the cached result when the same inputs occur again. In the context of calculating Fibonacci numbers, we can use memoization to avoid redundant calculations of the same Fibonacci numbers by caching the results of previous computations.

Let’s implement a memoized version of the Fibonacci function in C++:

```
#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int, int> memo; // A hash map to store computed Fibonacci numbers
int fibonacci(int n) {
if (n <= 1)
return n;
// Check if the result is already cached
if (memo.find(n) != memo.end())
return memo[n];
// Compute the Fibonacci number and store it in the memoization table
memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
return memo[n];
}
int main() {
int n = 6; // Calculate the 6th Fibonacci number
cout <<
"Fibonacci number at index " << n << " is: " << fibonacci(n) << endl;
return 0;
}
```

With memoization, the recursive calls are reduced, and each Fibonacci number is computed only once. This significantly improves the efficiency of the Fibonacci calculation, making it much faster than the naive recursive approach.

### 7. What is dynamic programming, and how does it relate to the Fibonacci sequence?

Dynamic programming is a technique used to solve complex problems by breaking them down into smaller overlapping subproblems and solving each subproblem only once. The solutions to subproblems are then stored and reused to avoid redundant calculations, which leads to improved time efficiency.

In the context of the Fibonacci sequence, dynamic programming can be applied by storing previously computed Fibonacci numbers and using them to calculate subsequent numbers.

Let’s implement the dynamic programming approach to calculate the nth Fibonacci number in C++:

```
#include <iostream>
using namespace std;
int fibonacci(int n) {
int fib[n + 1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
int main() {
int n = 6; // Calculate the 6th Fibonacci number
cout << "Fibonacci number at index " << n << " is: " << fibonacci(n) << endl;
return 0;
}
```

In this approach, we use an array `fib[]`

to store the calculated Fibonacci numbers. Starting from the 3rd index, each Fibonacci number is computed using the values at indices (i-1) and (i-2), and the result is stored in the array. By doing so, we avoid redundant calculations and achieve linear time complexity O(n).

### 8. Explain the iterative method to calculate Fibonacci numbers.

The iterative method to calculate Fibonacci numbers involves using a loop to iteratively compute the Fibonacci numbers from the bottom up, starting from the base cases (0 and 1).

Let’s implement the iterative approach to calculate the nth Fibonacci number in C++:

```
#include <iostream>
using namespace std;
int fibonacci(int n) {
if (n <= 1)
return n;
int prev = 0;
int current = 1;
for (int i = 2; i <= n; i++) {
int next = prev + current;
prev = current;
current = next;
}
return current;
}
int main() {
int n = 6; // Calculate the 6th Fibonacci number
cout << "Fibonacci number at index " << n << " is: " << fibonacci(n) << endl;
return 0;
}
```

In this approach, we use two variables (`prev`

and `current`

) to keep track of the last two Fibonacci numbers. In each iteration, we calculate the next Fibonacci number as the sum of the previous two, update the variables accordingly, and continue until we reach the desired index ‘n’. This iterative method also achieves linear time complexity O(n).

### 9. Can Fibonacci numbers be calculated in constant time? If yes, how?

No, Fibonacci numbers cannot be calculated in constant time for large values of ‘n’. The time complexity to calculate Fibonacci numbers is inherently exponential or linear, depending on the method used.

The recursive approach and iterative approach both have time complexity O(n), while the matrix exponentiation method has time complexity O(log n).

Although the matrix exponentiation method is more efficient than the other two, it still cannot achieve constant time complexity for Fibonacci number calculations.

### 10. What is matrix exponentiation, and how can it be used to compute Fibonacci numbers?

Matrix exponentiation is an efficient technique to compute the nth power of a square matrix in logarithmic time. This method can be used to compute Fibonacci numbers by representing the recurrence relation as a matrix equation.

The Fibonacci sequence can be expressed as a matrix equation:

```
| F(n) | | 1 1 | | F(n-1) |
| F(n-1) | = | 1 0 | * | F(n-2) |
```

To find the nth Fibonacci number, we can raise the matrix `{{1, 1}, {1, 0}}`

to the power of (n-1) using matrix exponentiation.

Let’s implement the matrix exponentiation method in C++ to compute the nth Fibonacci number:

```
#include <iostream>
#include <vector>
using namespace std;
typedef vector<vector<long long>> matrix;
const int MOD = 1000000007; // A large prime number to avoid integer overflow
matrix multiply(const matrix &A, const matrix &B) {
int n = A.size();
int m = A[0].size();
int p = B[0].size();
matrix C(n, vector<long long>(p, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < p; j++) {
for (int k = 0; k < m; k++) {
C[i][j] = (C[i][j] + (A[i][k] * B[k][j]) % MOD) % MOD;
}
}
}
return C;
}
matrix power(const matrix &A, int n) {
if (n == 1)
return A;
matrix halfPower = power(A, n / 2);
matrix result = multiply(halfPower, halfPower);
if (n % 2 == 1)
result = multiply(result, A);
return result;
}
int fibonacci(int n) {
if (n <= 0)
return 0;
matrix F = {{1, 1}, {1, 0}};
matrix Fn = power(F, n - 1);
return Fn[0][0];
}
int main() {
int n = 6; // Calculate the 6th Fibonacci number
cout << "Fibonacci number at index " << n << " is: " << fibonacci(n) << endl;
return 0;
}
```

The matrix exponentiation method reduces the time complexity to O(log n) for computing the nth Fibonacci number, making it the most efficient approach among the methods discussed so far.

### 11. How is the Fibonacci sequence used in sorting algorithms (like heapsort)?

Fibonacci numbers are used in sorting algorithms like heapsort to optimize the time complexity of building a heap. In heapsort, the first step is to build a binary heap from the input array. By using Fibonacci numbers, we can efficiently choose pivot elements during the heap-building process.

Here’s an example of how Fibonacci numbers are used in heapsort:

```
#include <iostream>
#include <vector>
using namespace std;
// Function to generate Fibonacci numbers up to 'n'
vector<int> generateFibonacci(int n) {
vector<int> fib;
fib.push_back(0);
fib.push_back(1);
int a = 0, b = 1;
while (a + b <= n) {
int next = a + b;
fib.push_back(next);
a = b;
b = next;
}
return fib;
}
// Function to build a max heap using Fibonacci numbers as pivot elements
void buildMaxHeap(vector<int>& arr) {
int n = arr.size();
vector<int> fib = generateFibonacci(n);
for (int i = fib.size() - 1; i >= 2; i--) {
int pivot = fib[i];
int j = pivot - 1;
while (j < n) {
// Perform a max heapify operation starting from index 'j'
int largest = j;
int left = 2 * j + 1;
int right = 2 * j + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != j) {
swap(arr[j], arr[largest]);
j = largest;
} else {
break;
}
}
}
}
// Function to perform heapsort on the input array
void heapSort(vector<int>& arr) {
buildMaxHeap(arr);
int n = arr.size();
for (int i = n - 1; i >= 1; i--) {
swap(arr[0], arr[i]);
buildMaxHeap(arr);
}
}
int main() {
vector<int> arr = {12, 11, 13, 5, 6, 7};
cout << "Original array: ";
for (int num : arr)
cout << num << " ";
cout << endl;
heapSort(arr);
cout << "Sorted array: ";
for (int num : arr)
cout << num << " ";
cout << endl;
return 0;
}
```

In the code above, the `generateFibonacci`

function generates Fibonacci numbers up to the size of the input array. Then, during the heap-building process in the `buildMaxHeap`

function, Fibonacci numbers are used as pivot elements to optimize the heapify operations.

### 12. What are some of the mathematical properties of the Fibonacci sequence?

The Fibonacci sequence has several interesting mathematical properties, some of which include:

**Golden Ratio:**As mentioned earlier, the ratio of consecutive Fibonacci numbers converges to the Golden Ratio (approximately 1.6180339887) as the index ‘n’ approaches infinity.**Divisibility:**For any two Fibonacci numbers F(m) and F(n) such that m > n, F(m) is divisible by F(n). This property is known as the “divisibility property.”**Cassini’s Identity:**Cassini’s identity states that the difference between two consecutive Fibonacci numbers is constant across the sequence. That is, for all ‘n,’ F(n+1) * F(n-1) – F(n)^2 = (-1)^n.**Binet’s Formula:**Binet’s formula provides a closed-form expression to calculate the nth Fibonacci number using the Golden Ratio: F(n) = (phi^n – (1-phi)^n) / sqrt(5) where phi is the Golden Ratio.**Fibonacci Prime:**A Fibonacci number is said to be a “Fibonacci prime” if it is a prime number. The sequence contains infinitely many Fibonacci primes.

### 13. How does the Fibonacci sequence relate to the concept of recursion?

The Fibonacci sequence is closely related to the concept of recursion because the calculation of each Fibonacci number depends on the values of two previous Fibonacci numbers. The recursive definition of the Fibonacci sequence is as follows:

F(n) = F(n-1) + F(n-2)

To calculate F(n), we need to calculate F(n-1) and F(n-2), both of which require calculating their respective preceding Fibonacci numbers, and so on until we reach the base cases F(0) and F(1).

Here’s an example of how recursion is used to calculate Fibonacci numbers:

```
#include <iostream>
using namespace std;
int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int n = 6; // Calculate the 6th Fibonacci number
cout << "Fibonacci number at index " << n << " is: " << fibonacci(n) << endl;
return 0;
}
```

In this example, the `fibonacci`

function is implemented using recursion. It recursively calls itself to calculate the nth Fibonacci number by summing the results of (n-1)th and (n-2)th Fibonacci numbers.

### 14. What is a Fibonacci heap in data structures?

A Fibonacci heap is a type of data structure that supports several efficient operations, making it useful for certain graph algorithms like Dijkstra’s algorithm and Prim’s algorithm.

The key characteristics of a Fibonacci heap are as follows:

**Amortized Constant Time Operations:**Many operations in a Fibonacci heap, such as insertion, deletion, and extracting the minimum element, have an amortized constant time complexity, making them very efficient.**Mergeable Heaps:**Two Fibonacci heaps can be efficiently merged together in constant time.**Decrease-Key Operation:**The value of a node in the heap can be decreased efficiently, allowing for efficient implementation of algorithms like Dijkstra’s shortest path algorithm.

### 15. What are Fibonacci retracements, and how are they used in financial markets?

Fibonacci retracements are a technical analysis tool used in financial markets to identify potential levels of support and resistance for a given asset’s price movement. The concept is based on the idea that after an asset’s price has made a significant move, it is likely to retrace or pull back to certain percentages of that move before continuing its trend.

The key Fibonacci retracement levels are derived from the Fibonacci sequence and the Golden Ratio. The most commonly used retracement levels are 23.6%, 38.2%, 50%, 61.8%, and 78.6%. These levels are obtained by dividing the vertical distance between two significant price points (usually a recent peak and a recent trough) by the Fibonacci ratios.

Here’s how Fibonacci retracements are used in financial markets:

**Identifying Trend Reversal Points:**Traders use Fibonacci retracement levels to identify potential points of trend reversal after a significant price movement. When an asset’s price retraces to one of these levels, it may indicate a potential support or resistance level, where the price could either bounce back or reverse its direction.**Placing Entry and Exit Points:**Traders use Fibonacci retracement levels to determine optimal entry and exit points for their trades. They may look to enter a long position (buy) when the price retraces to a Fibonacci support level and exit the position when the price reaches a resistance level.**Stop Loss Placement:**Fibonacci retracement levels can also help in setting stop loss orders. Traders may place stop loss orders slightly below a Fibonacci support level to protect their positions in case the price breaks below that level.**Combining with Other Technical Indicators:**Traders often combine Fibonacci retracements with other technical indicators, such as moving averages or trend lines, to strengthen their analysis and make more informed trading decisions.

## Coding Questions

### 16. Write a function to generate the nth Fibonacci number using recursion.

```
int fibonacciRecursive(int n) {
if (n <= 1)
return n;
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
```

### 17. Write a function to generate the nth Fibonacci number using dynamic programming.

```
int fibonacciDynamic(int n) {
int fib[n + 1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++)
fib[i] = fib[i - 1] + fib[i - 2];
return fib[n];
}
```

### 18. Write a function to generate the nth Fibonacci number using matrix exponentiation.

```
void multiplyMatrix(int mat1[2][2], int mat2[2][2]) {
int res[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
res[i][j] = 0;
for (int k = 0; k < 2; k++)
res[i][j] += mat1[i][k] * mat2[k][j];
}
}
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++)
mat1[i][j] = res[i][j];
}
}
int fibonacciMatrix(int n) {
int mat[2][2] = {{1, 1}, {1, 0}};
int res[2][2] = {{1, 0}, {0, 1}};
while (n > 0) {
if (n % 2 == 1)
multiplyMatrix(res, mat);
multiplyMatrix(mat, mat);
n /= 2;
}
return res[0][1];
}
```

### 19. Write a function to print the first n Fibonacci numbers.

```
void printFibonacciNumbers(int n) {
int fib[n];
fib[0] = 0;
fib[1] = 1;
cout << "Fibonacci Numbers: ";
cout << fib[0] << " " << fib[1] << " ";
for (int i = 2; i < n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
cout << fib[i] << " ";
}
cout << endl;
}
```

### 20. Write a function to calculate the sum of the first n Fibonacci numbers.

```
int sumOfFibonacciNumbers(int n) {
if (n <= 0)
return 0;
int fib[n + 1];
fib[0] = 0;
fib[1] = 1;
int sum = fib[0] + fib[1];
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
sum += fib[i];
}
return sum;
}
```

### 21. Write a program to check if a given number is a Fibonacci number.

```
bool is FibonacciNumber(int n) {
int a = 0, b = 1;
while (b < n) {
int temp = b;
b = a + b;
a = temp;
}
return (b == n);
}
```

### 22. Write a function to find the greatest common divisor (GCD) of two Fibonacci numbers.

```
int gcdOfFibonacciNumbers(int m, int n) {
if (m == 0)
return n;
return gcdOfFibonacciNumbers(n % m, m);
}
```

### 23. Write a function to compute the nth Fibonacci number modulo m.

```
int fibonacciModulo(int n, int m) {
if (n <= 1)
return n;
int fib[n + 1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++)
fib[i] = (fib[i - 1] + fib[i - 2]) % m;
return fib[n];
}
```

### 24. Write a function that returns the index of the first Fibonacci number with n digits.

```
int indexOfFibonacciNumberWithNDigits(int n) {
int a = 1, b = 1, index = 2;
while (b < pow(10, n - 1)) {
int temp = b;
b = a + b;
a = temp;
index++;
}
return index;
}
```

### 25. Write a function to find the number of ways to represent a number as a sum of Fibonacci numbers.

```
int waysToRepresentAsSumOfFibonacciNumbers(int n) {
int fib[100];
fib[0] = 0;
fib[1] = 1;
int count = 0;
int sum = 0;
while (fib[count] <= n) {
sum += fib[count];
if (sum == n)
return count + 1;
count++;
}
return count;
}
```

### 26. Write a function to generate Fibonacci numbers that fit within a given range.

```
void generateFibonacciInRange(int start, int end) {
int a = 0, b = 1;
while (a <= end) {
if (a >= start)
cout << a << " ";
int temp = b;
b = a + b;
a = temp;
}
cout << endl;
}
```

### 27. Write a function to find the minimum number of Fibonacci numbers whose sum is equal to a given number.

```
int minimumFibonacciNumbersForSum(int n) {
int fib[100];
fib[0] = 0;
fib[1] = 1;
int count = 0;
while (n > 0) {
int i = 2;
while (fib[i] <= n)
i++;
count++;
n -= fib[i - 1];
}
return count;
}
```

### 28. Write a function to find the last digit of the nth Fibonacci number.

```
int lastDigitOfFibonacciNumber(int n) {
if (n <= 1)
return n;
int a = 0, b = 1;
for (int i = 2;i <= n; i++) {
int temp = (a + b) % 10;
a = b;
b = temp;
}
return b;
}
```

### 29. Write a function to find the number of digits in the nth Fibonacci number.

```
int numberOfDigitsInFibonacciNumber(int n) {
if (n <= 1)
return 1;
double digits = ((n * log10(1.6180339887498948)) - ((log10(5)) / 2));
return ceil(digits);
}
```

### 30. Write a function to find the Fibonacci series in reverse order.

```
void printFibonacciReverse(int n) {
int fib[n];
fib[0] = 0;
fib[1] = 1;
cout << "Fibonacci Numbers (in reverse order): ";
for (int i = n - 1; i >= 0; i--) {
fib[i] = fib[i + 2] - fib[i + 1];
cout << fib[i] << " ";
}
cout << endl;
}
```

## MCQ Questions

### 1. What is the Fibonacci series?

a) A series of prime numbers

b) A series of even numbers

c) A series of numbers in which each number is the sum of the two preceding ones

d) A series of odd numbers

Answer: c) A series of numbers in which each number is the sum of the two preceding ones

### 2. What are the first two numbers in the Fibonacci series?

a) 0, 1

b) 1, 2

c) 1, 1

d) 0, 2

Answer: a) 0, 1

### 3. What is the next number in the Fibonacci series after 1, 1?

a) 3

b) 2

c) 4

d) 5

Answer: d) 5

### 4. What is the Fibonacci number after 13?

a) 18

b) 20

c) 21

d) 23

Answer: c) 21

### 5. What is the value of the 10th Fibonacci number?

a) 45

b) 55

c) 89

d) 144

Answer: b) 55

### 6. Which approach is commonly used to calculate Fibonacci numbers recursively?

a) Dynamic programming

b) Binary search

c) Depth-first search

d) Divide and conquer

Answer: d) Divide and conquer

### 7. Which of the following algorithms can efficiently compute the nth Fibonacci number in O(n) time complexity?

a) Recursive algorithm

b) Brute force algorithm

c) Matrix exponentiation algorithm

d) Greedy algorithm

Answer: c) Matrix exponentiation algorithm

### 8. What is the time complexity of the matrix exponentiation algorithm to calculate the nth Fibonacci number?

a) O(1)

b) O(n)

c) O(log n)

d) O(n^2)

Answer: c) O(log n)

### 9. Which of the following methods is an efficient approach to calculate Fibonacci numbers without using recursion?

a) Breadth-first search

b) Sieve of Eratosthenes

c) Iterative approach

d) Depth-first search

Answer: c) Iterative approach

### 10. What is the value of the sum of the first 10 Fibonacci numbers?

a) 44

b) 88

c) 89

d) 144

Answer: a) 44

### 11. Which of the following series is similar to the Fibonacci series?

a) Pascal’s triangle

b) Harmonic series

c) Geometric series

d) Lucas series

Answer: d) Lucas series

### 12. In the Fibonacci series, what is the ratio of consecutive Fibonacci numbers as they approach infinity?

a) 1:2

b) 2:3

c) 1:1

d) 1:phi (Golden ratio)

Answer: d) 1:phi (Golden ratio)

### 13. Which of the following is NOT a property of the Fibonacci series?

a) Each number is the sum of the two preceding ones

b) The ratio of consecutive Fibonacci numbers approaches a constant value

c) The Fibonacci series is an arithmetic progression

d) The Fibonacci series starts with 0 and 1

Answer: c) The Fibonacci series is an arithmetic progression

### 14 . What is the largest Fibonacci number that can be represented using 32 bits?

a) 1836311903

b) 267914296

c) 165580141

d) 102334155

Answer: b) 267914296

### 15. Which of the following algorithms can efficiently calculate the nth Fibonacci number using memoization?

a) Depth-first search

b) Greedy algorithm

c) Dynamic programming

d) Breadth-first search

Answer: c) Dynamic programming

### 16. What is the Fibonacci number before 377?

a) 233

b) 2584

c) 144

d) 987

Answer: b) 2584

### 17. What is the Fibonacci number after 6765?

a) 10946

b) 987

c) 4181

d) 46368

Answer: a) 10946

### 18. Which of the following algorithms can calculate the nth Fibonacci number with the lowest time complexity?

a) Recursive algorithm

b) Brute force algorithm

c) Matrix exponentiation algorithm

d) Dynamic programming algorithm

Answer: c) Matrix exponentiation algorithm

### 19. What is the Fibonacci number after 89?

a) 144

b) 233

c) 1597

d) 377

Answer: c) 1597

### 20. Which of the following properties is NOT true for the Fibonacci series?

a) The sum of any two consecutive Fibonacci numbers is equal to the next Fibonacci number.

b) The ratio of consecutive Fibonacci numbers approaches the golden ratio.

c) Fibonacci numbers can be negative.

d) The Fibonacci series starts with 0 and 1.

Answer: c) Fibonacci numbers can be negative.