Home » Interview coding problems/challenges

Largest Fibonacci Subsequence

In this article, we are going to see how to find largest Fibonacci subsequence in a given array? This problem has been featured in Facebook interview. Submitted by Radib Kar, on March 16, 2019

Problem statement

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

Solution

What is Subsequence?

A subsequence is not same as subarray. A subarray means collection of contiguous elements from an array. Where subsequence means a set of elements from the array, let's say S,

Where ant two pair (a_i,b_j)(where, i and j are their respective indices from original array and a and b be their respective value) i<j

Let's say A=1, 2, 3, 4, 5

A subsequence Scan be {1, 3, 5} but not {2, 1, 4}

Whereas both are not subarrays.

So to find the subsequence where elements are Fibonacci number we need to check the subsequent elements Fibonacci number or not. If element is Fibonacci we can add to our subsequence.

Pre-requisite:

1. Input array A
2. A Boolean function isFibo(n) that checks whether n is Fibonacci or not

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

Explanation with example

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