Length of longest subsequence of Fibonacci Numbers in an Array
Given an array arr containing non-negative integers, the task is to print the length of the longest subsequence of Fibonacci numbers in this array.
Examples:
Input: arr[] = { 3, 4, 11, 2, 9, 21 }
Output: 3
Here, the subsequence is {3, 2, 21} and hence the answer is 3.
Input: arr[] = { 6, 4, 10, 13, 9, 25 }
Output: 1
Here, the subsequence is {1} and hence the answer is 1.
Approach:
- Build hash table containing all the Fibonacci numbers which will be used to test a number in O(1) time.
- Now, we will traverse through the given array.
- We will include all the Fibonacci numbers that we encounter during our traversal into the longest subsequence and hence increase the answer by 1 for every encounter of a Fibonacci number.
- Once the entire initial array has been encountered, we have the length of the longest subsequence containing only Fibonacci numbers with us.
Below is the implementation of the above approach:
C++
// C++ program to find the length // of longest subsequence of // Fibonacci Numbers in an Array #include <bits/stdc++.h> using namespace std; #define N 100005 // Function to create hash table // to check Fibonacci numbers void createHash(set< int >& hash, int maxElement) { int prev = 0, curr = 1; hash.insert(prev); hash.insert(curr); while (curr <= maxElement) { int temp = curr + prev; hash.insert(temp); prev = curr; curr = temp; } } // Function to find the longest // subsequence containing // all Fibonacci numbers int longestFibonacciSubsequence( int arr[], int n) { set< int > hash; createHash( hash, *max_element(arr, arr + n)); int answer = 0; for ( int i = 0; i < n; i++) { if (hash.find(arr[i]) != hash.end()) { answer++; } } return answer; } // Driver code int main() { int arr[] = { 3, 4, 11, 2, 9, 21 }; int n = sizeof (arr) / sizeof (arr[0]); // Function call cout << longestFibonacciSubsequence(arr, n) << endl; return 0; } |
Java
// Java program to find the length // of longest subsequence of // Fibonacci Numbers in an Array import java.util.*; class GFG{ static final int N = 100005 ; // Function to create hash table // to check Fibonacci numbers static void createHash(HashSet<Integer> hash, int maxElement) { int prev = 0 , curr = 1 ; hash.add(prev); hash.add(curr); while (curr <= maxElement) { int temp = curr + prev; hash.add(temp); prev = curr; curr = temp; } } // Function to find the longest // subsequence containing // all Fibonacci numbers static int longestFibonacciSubsequence( int arr[], int n) { HashSet<Integer> hash = new HashSet<Integer>(); createHash( hash,Arrays.stream(arr).max().getAsInt()); int answer = 0 ; for ( int i = 0 ; i < n; i++) { if (hash.contains(arr[i])) { answer++; } } return answer; } // Driver code public static void main(String[] args) { int arr[] = { 3 , 4 , 11 , 2 , 9 , 21 }; int n = arr.length; // Function call System.out.print(longestFibonacciSubsequence(arr, n) + "\n" ); } } // This code contributed by Princi Singh |
Python 3
# Python 3 program to find the length # of longest subsequence of # Fibonacci Numbers in an Array N = 100005 # Function to create hash table # to check Fibonacci numbers def createHash( hash ,maxElement): prev = 0 curr = 1 hash .add(prev) hash .add(curr) while (curr < = maxElement): temp = curr + prev hash .add(temp) prev = curr curr = temp # Function to find the longest # subsequence containing # all Fibonacci numbers def longestFibonacciSubsequence(arr, n): hash = set () createHash( hash , max (arr)) answer = 0 for i in range (n): if (arr[i] in hash ): answer + = 1 return answer # Driver code if __name__ = = '__main__' : arr = [ 3 , 4 , 11 , 2 , 9 , 21 ] n = len (arr) # Function call print (longestFibonacciSubsequence(arr, n)) # This code is contributed by Surendra_Gangwar |
C#
// C# program to find the length // of longest subsequence of // Fibonacci Numbers in an Array using System; using System.Linq; using System.Collections.Generic; class GFG{ static readonly int N = 100005; // Function to create hash table // to check Fibonacci numbers static void createHash(HashSet< int > hash, int maxElement) { int prev = 0, curr = 1; hash.Add(prev); hash.Add(curr); while (curr <= maxElement) { int temp = curr + prev; hash.Add(temp); prev = curr; curr = temp; } } // Function to find the longest // subsequence containing // all Fibonacci numbers static int longestFibonacciSubsequence( int []arr, int n) { HashSet< int > hash = new HashSet< int >(); createHash(hash,arr.Max()); int answer = 0; for ( int i = 0; i < n; i++) { if (hash.Contains(arr[i])) { answer++; } } return answer; } // Driver code public static void Main(String[] args) { int []arr = { 3, 4, 11, 2, 9, 21 }; int n = arr.Length; // Function call Console.Write(longestFibonacciSubsequence(arr, n) + "\n" ); } } // This code is contributed by sapnasingh4991 |
Javascript
<script> // Javascript program to find the length // of longest subsequence of // Fibonacci Numbers in an Array let N = 100005; // Function to create hash table // to check Fibonacci numbers function createHash(hash, maxElement) { let prev = 0, curr = 1; hash.add(prev); hash.add(curr); while (curr <= maxElement) { let temp = curr + prev; hash.add(temp); prev = curr; curr = temp; } } // Function to find the longest // subsequence containing // all Fibonacci numbers function longestFibonacciSubsequence(arr, n) { let hash = new Set(); createHash(hash, Math.max(...arr)); let answer = 0; for (let i = 0; i < n; i++) { if (hash.has(arr[i])) { answer++; } } return answer; } // Driver code let arr = [ 3, 4, 11, 2, 9, 21 ]; let n = arr.length; // Function call document.write(longestFibonacciSubsequence(arr, n) + "\n" ); // This code is contributed by sanjoy_62. </script> |
Output:
3