Dado un arreglo A que contiene números enteros, la tarea es encontrar la longitud del subarreglo de Fibonacci más largo formado al eliminar solo un elemento del arreglo.
Ejemplos:
Entrada: arr[] = { 2, 8, 5, 7, 3, 5, 7 }
Salida: 5
Explicación:
si eliminamos el número 7 en el índice 3, entonces el conjunto restante contiene un subarreglo de Fibonacci {2, 8, 5 , 3, 5} de longitud 5, que es el máximo.
Entrada: arr[] = { 2, 3, 6, 1 }
Salida: 3
Explicación:
si eliminamos el número 6 en el índice 2, entonces el conjunto restante contiene un subarreglo de Fibonacci {2, 3, 1} de longitud 3, que es máximo.
Enfoque: el problema mencionado anteriormente se puede resolver contando los números de Fibonacci contiguos justo antes de cada índice y justo después de cada índice.
- Ahora recorra la array nuevamente y encuentre un índice para el cual el recuento de números de Fibonacci antes y después sea máximo.
- Para verificar los números de Fibonacci , construiremos una tabla hash que contenga todos los números de Fibonacci menores o iguales al valor máximo en la array para probar un número en tiempo O(1).
A continuación se muestra la implementación del enfoque anterior:
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 numbers
void 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 subarray
int 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 code
int 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 numbers
import java.util.*;
class GFG{
static final int N = 100000;
// Function to create hash table
// to check for Fibonacci numbers
static 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 subarray
static 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 code
public 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 numbers
using System;
using System.Linq;
using System.Collections.Generic;
class GFG{
static readonly int N = 100000;
// Function to create hash table
// to check for Fibonacci numbers
static 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 subarray
static 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 code
public 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 numbers
let N = 100000;
// Function to create hash table
// to check for Fibonacci numbers
function 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 subarray
function 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>
Producción:
5
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA