Subconjunto más grande cuyos elementos son números de Fibonacci

Dada una array con un número positivo, la tarea es encontrar el subconjunto más grande de la array que contiene elementos que son números de Fibonacci .
preguntado en facebook 

Ejemplos: 

Input : arr[] = {1, 4, 3, 9, 10, 13, 7};
Output : subset[] = {1, 3, 13}
The output three numbers are Fibonacci
numbers.

Input  : arr[] = {0, 2, 8, 5, 2, 1, 4, 
                  13, 23};
Output : subset[] = {0, 2, 8, 5, 2, 1, 
                    13}

Una solución simple es iterar a través de todos los elementos de la array dada. Para cada número, comprueba si es Fibonacci o no. Si es así, añádelo al resultado.

Implementación:

# python3 program to find largest Fibonacci subset
# Prints largest subset of an array whose
# all elements are fibonacci numbers
def findFibSubset(arr, n):
  #Now iterate through all elements of the array..
  for i in range(n):
    #we are using the property of fibonacci series to check arr[i] is a
    # fib number or not by checking whether any one out of 5(n^2)+4 and 5(n^2)-4
    # is a perfect square or not.
    fact1=5*(arr[i]**2)+4
    fact2=5*(arr[i]**2)-4
    if int(fact1**(.5))**2==fact1 or int(fact2**(.5))**2==fact2:
      print(arr[i],end=" ")
  return None
          
         
 # Driver code
if __name__ == "__main__":
  
    arr = [4, 2, 8, 5, 20, 1, 40, 13, 23]
    n = len(arr)
    findFibSubset(arr, n)      
 # This code is contributed by Rajat Kumar (GLA University)

2 8 5 1 13 

Complejidad temporal : la complejidad temporal de la solución anterior es O(n) y la complejidad espacial es O(1) .

A continuación se muestra otra solución basada en hashing. 

1. Encuentra max en la array
2. Genere números de Fibonacci hasta el máximo y guárdelos en una tabla hash. 
3. Recorra la array nuevamente si el número está presente en la tabla hash y luego agréguelo al resultado.

Implementación:

// C++ program to find largest Fibonacci subset
#include<bits/stdc++.h>
using namespace std;
 
// Prints largest subset of an array whose
// all elements are fibonacci numbers
void findFibSubset(int arr[], int n)
{
    // Find maximum element in arr[]
    int max = *std::max_element(arr, arr+n);
 
    // Generate all Fibonacci numbers till
    // max and store them in hash.
    int a = 0, b = 1;
    unordered_set<int> hash;
    hash.insert(a);
    hash.insert(b);
    while (b < max)
    {
        int c = a + b;
        a = b;
        b = c;
        hash.insert(b);
    }
 
    // Npw iterate through all numbers and
    // quickly check for Fibonacci using
    // hash.
    for (int i=0; i<n; i++)
        if (hash.find(arr[i]) != hash.end())
            printf("%d ", arr[i]);
}
 
// Driver code
int main()
{
    int arr[] = {4, 2, 8, 5, 20, 1, 40, 13, 23};
    int n = sizeof(arr)/sizeof(arr[0]);
    findFibSubset(arr, n);
    return 0;
}

// Java program to find
// largest Fibonacci subset
import java.util.*;
 
class GFG
{
    // Prints largest subset of an array whose
    // all elements are fibonacci numbers
    public static void findFibSubset(Integer[] x)
    {
        Integer max = Collections.max(Arrays.asList(x));
        List<Integer> fib = new ArrayList<Integer>();
        List<Integer> result = new ArrayList<Integer>();
         
        // Generate all Fibonacci numbers
        // till max and store them
        Integer a = 0;
        Integer b = 1;
        while (b < max){
            Integer c = a + b;
            a=b;
            b=c;
            fib.add(c);
        }
     
        // Now iterate through all numbers and
        // quickly check for Fibonacci
        for (Integer i = 0; i < x.length; i++){
        if(fib.contains(x[i])){
            result.add(x[i]);
        }    
        }
        System.out.println(result);
    }
 
    // Driver code
    public static void main(String args[])
    {
        Integer[] a = {4, 2, 8, 5, 20, 1, 40, 13, 23};
        findFibSubset(a);
    }
}
 
// This code is contributed by prag93

# python3 program to find largest Fibonacci subset
  
# Prints largest subset of an array whose
# all elements are fibonacci numbers
def findFibSubset(arr, n):
 
    # Find maximum element in arr[]
    m= max(arr)
  
    # Generate all Fibonacci numbers till
    # max and store them in hash.
    a = 0
    b = 1
    hash = []
    hash.append(a)
    hash.append(b)
    while (b < m):
     
        c = a + b
        a = b
        b = c
        hash.append(b)
     
  
    # Npw iterate through all numbers and
    # quickly check for Fibonacci using
    # hash.
    for i in range (n):
        if arr[i] in hash :
            print( arr[i],end=" ")
  
# Driver code
if __name__ == "__main__":
 
    arr = [4, 2, 8, 5, 20, 1, 40, 13, 23]
    n = len(arr)
    findFibSubset(arr, n)

// C# program to find
// largest Fibonacci subset
using System;
using System.Linq;
using System.Collections.Generic;
     
class GFG
{
    // Prints largest subset of an array whose
    // all elements are fibonacci numbers
    public static void findFibSubset(int[] x)
    {
        int max = x.Max();
        List<int> fib = new List<int>();
        List<int> result = new List<int>();
         
        // Generate all Fibonacci numbers
        // till max and store them
        int a = 0;
        int b = 1;
        while (b < max)
        {
            int c = a + b;
            a = b;
            b = c;
            fib.Add(c);
        }
     
        // Now iterate through all numbers and
        // quickly check for Fibonacci
        for (int i = 0; i < x.Length; i++)
        {
            if(fib.Contains(x[i]))
            {
                result.Add(x[i]);
            }    
        }
        foreach(int i in result)
            Console.Write(i + " ");
    }
 
    // Driver code
    public static void Main(String []args)
    {
        int[] a = {4, 2, 8, 5, 20, 1, 40, 13, 23};
        findFibSubset(a);
    }
}
 
// This code is contributed by PrinciRaj1992

<script>
  
// Javascript program to find largest Fibonacci subset
 
// Prints largest subset of an array whose
// all elements are fibonacci numbers
function findFibSubset(arr, n)
{
    // Find maximum element in arr[]
    var max = arr.reduce((a,b)=>Math.max(a,b))
 
    // Generate all Fibonacci numbers till
    // max and store them in hash.
    var a = 0, b = 1;
    var hash = new Set();
    hash.add(a);
    hash.add(b);
    while (b < max)
    {
        var c = a + b;
        a = b;
        b = c;
        hash.add(b);
    }
 
    // Npw iterate through all numbers and
    // quickly check for Fibonacci using
    // hash.
    for (var i=0; i<n; i++)
        if (hash.has(arr[i]))
            document.write( arr[i]
            + " ");
}
 
// Driver code
var arr = [4, 2, 8, 5, 20, 1, 40, 13, 23];
var n = arr.length;
findFibSubset(arr, n);
 
// This code is contributed by famously.
</script>

2 8 5 1 13 

Complejidad del tiempo : la complejidad del tiempo del código anterior es O (n) y la complejidad del espacio también será O (n) ya que lo estamos almacenando en el mapa hash cada número de fibonacci en el mapa hash…

Este artículo es una contribución de DANISH_RAZA . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.