Largest subset whose all elements are Fibonacci numbers

by Online Tutorials Library July 14, 2022

Largest subset whose all elements are Fibonacci numbers

What is Fibonacci Series

The Fibonacci numbers are the numbers in the integer sequence shown below.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

The recurrence relation defines the sequence Fn of Fibonacci numbers in mathematical terms.

with seed values

F₀ = 0 and F₁ = 1.

Largest subset whose all elements are Fibonacci numbers

Given a positive number array, the task is to find the largest subset of the array that contains elements that are Fibonacci numbers.

Examples

  Input : arr[] = {1, 4, 3, 9, 10, 13, 7};  Output : subset[] = {1, 3, 13}  The output three numbers are Fibonacci numbers.    Input  : arr[] = {0, 2, 8, 5, 2, 1, 4, 13, 23};  Output : subset[] = {0, 2, 8, 5, 2, 1, 13}  

Iterating through all elements of a given array is a simple solution. Check each number to see if it is Fibonacci or not. If so, include it in the final result.

Program in C++

// C++ program to find largest Fibonacci subset  #include  using namespace std;    // Prints largest subset of an array whose  // all elements are fibonacci numbers  void findFibSubset(int arr[], int n)  {  // Find maximum element in arr[]  int max = *std::max_element(arr, arr+n);    // Generate all Fibonacci numbers till  // max and store them in hash.  int a = 0, b = 1;  unordered_set hash;  hash.insert(a);  hash.insert(b);  while (b < max)  {  int c = a + b;  a = b;  b = c;  hash.insert(b);  }    // Npw iterate through all numbers and  // quickly check for Fibonacci using  // hash.  for (int i=0; i;>

Output

2 8 5 1 13

Time Complexity: The above code has an O(n) time complexity and an O(n) space complexity because we store each fibonacci number in a hash map.

Next Topic#

Largest subset whose all elements are Fibonacci numbers

Largest subset whose all elements are Fibonacci numbers

What is Fibonacci Series

Largest subset whose all elements are Fibonacci numbers

Examples

Program in C++

SQL Interview Questions (2022)

Bridge Pattern

You may also like