Given an array A containing integers, the task is to find the length of longest Fibonacci subarray formed by removing only one element from the array.
Examples:
Input: arr[] = { 2, 8, 5, 7, 3, 5, 7 }
Output: 5
Explanation:
If we remove the number 7 at index 3, then the remaining array contains a Fibonacci subarray {2, 8, 5, 3, 5} of length 5, which is maximum.
Input: arr[] = { 2, 3, 6, 1 }
Output: 3
Explanation:
If we remove the number 6 at index 2, then the remaining array contains a Fibonacci subarray {2, 3, 1} of length 3, which is maximum.
Approach: The above-mentioned problem can be solved by counting the contiguous Fibonacci numbers just before every index and just after every index.
- Now traverse the array again and find an index for which counts of Fibonacci numbers after and before is maximum.
- In order to check for Fibonacci numbers, we will build a hash table containing all the Fibonacci numbers less than or equal to the maximum value in the array to test a number in O(1) time.
Below is the implementation of the above approach:
CPP
// C++ program to find length of the longest// subarray with all fibonacci numbers#include <bits/stdc++.h>using namespace std;#define N 100000// Function to create hash table// to check for Fibonacci numbersvoid createHash(set<int>& hash, int maxElement){ // Insert first two fibonacci numbers int prev = 0, curr = 1; hash.insert(prev); hash.insert(curr); while (curr <= maxElement) { // Summation of last two numbers int temp = curr + prev; hash.insert(temp); // Update the variable each time prev = curr; curr = temp; }}// Function to find the// longest fibonacci subarrayint longestFibSubarray( int arr[], int n){ // Find maximum value in the array int max_val = *max_element(arr, arr + n); // Creating a set // containing Fibonacci numbers set<int> hash; createHash(hash, max_val); int left[n], right[n]; int fibcount = 0, res = -1; // Left array is used to count number of // continuous fibonacci numbers starting // from left of current element for (int i = 0; i < n; i++) { left[i] = fibcount; // Check if current element // is a fibonacci number if (hash.find(arr[i]) != hash.end()) { fibcount++; } else fibcount = 0; } // Right array is used to count number of // continuous fibonacci numbers starting // from right of current element fibcount = 0; for (int i = n - 1; i >= 0; i--) { right[i] = fibcount; // Check if current element // is a fibonacci number if (hash.find(arr[i]) != hash.end()) { fibcount++; } else fibcount = 0; } for (int i = 0; i < n; i++) res = max( res, left[i] + right[i]); return res;}// Driver codeint main(){ int arr[] = { 2, 8, 5, 7, 3, 5, 7 }; int n = sizeof(arr) / sizeof(arr[0]); cout << longestFibSubarray(arr, n) << endl; return 0;} |
Java
// Java program to find length of the longest// subarray with all fibonacci numbersimport java.util.*;class GFG{static final int N = 100000; // Function to create hash table// to check for Fibonacci numbersstatic void createHash(HashSet<Integer> hash, int maxElement){ // Insert first two fibonacci numbers int prev = 0, curr = 1; hash.add(prev); hash.add(curr); while (curr <= maxElement) { // Summation of last two numbers int temp = curr + prev; hash.add(temp); // Update the variable each time prev = curr; curr = temp; }} // Function to find the// longest fibonacci subarraystatic int longestFibSubarray( int arr[], int n){ // Find maximum value in the array int max_val = Arrays.stream(arr).max().getAsInt(); // Creating a set // containing Fibonacci numbers HashSet<Integer> hash = new HashSet<Integer>(); createHash(hash, max_val); int []left = new int[n]; int []right = new int[n]; int fibcount = 0, res = -1; // Left array is used to count number of // continuous fibonacci numbers starting // from left of current element for (int i = 0; i < n; i++) { left[i] = fibcount; // Check if current element // is a fibonacci number if (hash.contains(arr[i])) { fibcount++; } else fibcount = 0; } // Right array is used to count number of // continuous fibonacci numbers starting // from right of current element fibcount = 0; for (int i = n - 1; i >= 0; i--) { right[i] = fibcount; // Check if current element // is a fibonacci number if (hash.contains(arr[i])) { fibcount++; } else fibcount = 0; } for (int i = 0; i < n; i++) res = Math.max( res, left[i] + right[i]); return res;} // Driver codepublic static void main(String[] args){ int arr[] = { 2, 8, 5, 7, 3, 5, 7 }; int n = arr.length; System.out.print(longestFibSubarray(arr, n) +"\n"); }}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to find length of the longest # subarray with all fibonacci numbers N = 100000# Function to create hash table # to check for Fibonacci numbers def createHash(hash, maxElement) : # Insert first two fibonacci numbers prev = 0 curr = 1 hash.add(prev) hash.add(curr) while (curr <= maxElement) : # Summation of last two numbers temp = curr + prev hash.add(temp) # Update the variable each time prev = curr curr = temp # Function to find the # longest fibonacci subarray def longestFibSubarray(arr, n) : # Find maximum value in the array max_val = max(arr) # Creating a set # containing Fibonacci numbers hash = {int} createHash(hash, max_val) left = [ 0 for i in range(n)] right = [ 0 for i in range(n)] fibcount = 0 res = -1 # Left array is used to count number of # continuous fibonacci numbers starting # from left of current element for i in range(n) : left[i] = fibcount # Check if current element # is a fibonacci number if (arr[i] in hash) : fibcount += 1 else: fibcount = 0 # Right array is used to count number of # continuous fibonacci numbers starting # from right of current element fibcount = 0 for i in range(n-1,-1,-1) : right[i] = fibcount # Check if current element # is a fibonacci number if (arr[i] in hash) : fibcount += 1 else: fibcount = 0 for i in range(0,n) : res = max(res, left[i] + right[i]) return res# Driver code arr = [ 2, 8, 5, 7, 3, 5, 7 ] n = len(arr)print(longestFibSubarray(arr, n))# This code is contributed by Sanjit_Prasad |
C#
// C# program to find length of the longest// subarray with all fibonacci numbersusing System;using System.Linq;using System.Collections.Generic;class GFG{static readonly int N = 100000; // Function to create hash table// to check for Fibonacci numbersstatic void createHash(HashSet<int> hash, int maxElement){ // Insert first two fibonacci numbers int prev = 0, curr = 1; hash.Add(prev); hash.Add(curr); while (curr <= maxElement) { // Summation of last two numbers int temp = curr + prev; hash.Add(temp); // Update the variable each time prev = curr; curr = temp; }} // Function to find the// longest fibonacci subarraystatic int longestFibSubarray( int []arr, int n){ // Find maximum value in the array int max_val = arr.Max(); // Creating a set // containing Fibonacci numbers HashSet<int> hash = new HashSet<int>(); createHash(hash, max_val); int []left = new int[n]; int []right = new int[n]; int fibcount = 0, res = -1; // Left array is used to count number of // continuous fibonacci numbers starting // from left of current element for (int i = 0; i < n; i++) { left[i] = fibcount; // Check if current element // is a fibonacci number if (hash.Contains(arr[i])) { fibcount++; } else fibcount = 0; } // Right array is used to count number of // continuous fibonacci numbers starting // from right of current element fibcount = 0; for (int i = n - 1; i >= 0; i--) { right[i] = fibcount; // Check if current element // is a fibonacci number if (hash.Contains(arr[i])) { fibcount++; } else fibcount = 0; } for (int i = 0; i < n; i++) res = Math.Max( res, left[i] + right[i]); return res;} // Driver codepublic static void Main(String[] args){ int []arr = { 2, 8, 5, 7, 3, 5, 7 }; int n = arr.Length; Console.Write(longestFibSubarray(arr, n) +"\n"); }}// This code is contributed by sapnasingh4991 |
Javascript
<script>// Javascript program to find length of the longest// subarray with all fibonacci numberslet N = 100000; // Function to create hash table// to check for Fibonacci numbersfunction createHash( hash, maxElement){ // Insert first two fibonacci numbers let prev = 0, curr = 1; hash.add(prev); hash.add(curr); while (curr <= maxElement) { // Summation of last two numbers let temp = curr + prev; hash.add(temp); // Update the variable each time prev = curr; curr = temp; }} // Function to find the// longest fibonacci subarrayfunction longestFibSubarray(arr, n){ // Find maximum value in the array let max_val = Math.max(...arr); // Creating a set // containing Fibonacci numbers let hash = new Set(); createHash(hash, max_val); let left = Array.from({length: n}, (_, i) => 0); let right = Array.from({length: n}, (_, i) => 0); let fibcount = 0, res = -1; // Left array is used to count number of // continuous fibonacci numbers starting // from left of current element for (let i = 0; i < n; i++) { left[i] = fibcount; // Check if current element // is a fibonacci number if (hash.has(arr[i])) { fibcount++; } else fibcount = 0; } // Right array is used to count number of // continuous fibonacci numbers starting // from right of current element fibcount = 0; for (let i = n - 1; i >= 0; i--) { right[i] = fibcount; // Check if current element // is a fibonacci number if (hash.has(arr[i])) { fibcount++; } else fibcount = 0; } for (let i = 0; i < n; i++) res = Math.max( res, left[i] + right[i]); return res;}// Driver code let arr = [ 2, 8, 5, 7, 3, 5, 7 ]; let n = arr.length; document.write(longestFibSubarray(arr, n) +"<br/>"); // This code is contributed by sanjoy_62.</script> |
Output
5
Time Complexity: O(n + log(m)), where n is the size of the given array and m is the maximum element in the array.
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
