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

- Input array
**A** - 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

**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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.

Learn PCB Designing: PCB DESIGNING TUTORIAL