Q:

Given an array with positive number the task to find the largest subsequence from array that contain elements which are Fibonacci numbers

Given an array with positive number the task to find the largest subsequence from array that contain elements which are Fibonacci numbers.

Example:

```    Input array:
2 4 5 8 13 15 21

Output:
2 5 8 13 21```

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

Algorithm:

```    Declare subsequence S
For i=0:Array length -1
IF isFibo(A[i])
Add A[i] to S
END IF
END For
```

Now the most interesting is isFibo(n) function. It really looks like nasty to check whether a given number is Fibonacci or not. But mathematics has been such a nice boon that there exists a lovely relation between Fibonacci number and golden ratio, which actually resulted in a nice formula to check for a number whether Fibonacci number or not

If 5*n*n +4 or 5*n*n -4 is perfect square then n is a Fibonacci number. For details check over here: Search a Fibonacci number

Example with explanation:

```Input array:
2 4 5 8 13 15 21
2 is Fibonacci no: 5*2*2-4 is perfect square(5*2*2-4=16)
5 is Fibonacci no: 5*5*5-4 is perfect square(5*5*5-4=121)
8 is Fibonacci no: 5*8*8+4 is perfect square(5*8*8+4=324)
13 is Fibonacci no: 5*13*13-4 is perfect square(5*13*13-4=841)
21 is Fibonacci no: 5*21*21+4 is perfect square(5*21*21+4=2209)

Subsequence is:
2 5 8 13 21
```

C++ implementation

``````#include <bits/stdc++.h>
using namespace std;

//checking a is Fibonacci or not
bool isFibo(int a){
int t1=sqrt(5*a*a+4);
int t2=sqrt(5*a*a-4);

//checking whether t1 or t2 is perfect square
if(t1*t1==(5*a*a+4))
return true;

if(t2*t2==(5*a*a-4))
return true;

return false;
}

void largestSubsequence(vector<int> a,int n)
{
for(int i=0;i<n;i++)
if(isFibo(a[i]))
cout<<a[i]<<" ";
}

int main()
{
int n,item;
cout<<"enter no of elements\n";
scanf("%d",&n);

cout<<"Enter array elements\n";
vector<int> a;

for(int j=0;j<n;j++){
scanf("%d",&item);
a.push_back(item);
}

cout<<"Largest fibonacci Subsequence is:\n";
largestSubsequence(a,n);
cout<<endl;

return 0;
}
``````

Output

```enter no of elements
7
Enter array elements
2 4 5 8 13 15 21
Largest fibonacci Subsequence is:
2 5 8 13 21```

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)