Eliminar todos los números de fibonacci de la array dada

Dada una array arr[] de N enteros, la tarea es eliminar todos los números de Fibonacci presentes en la array.
Ejemplos: 
 

Entrada: arr[] = {4, 6, 5, 3, 8, 7, 10, 11, 14, 15} 
Salida: 4 6 7 10 11 14 15 
Explicación: 
La array contiene 3 valores de datos de Fibonacci 5, 3 y 8
Estos valores se han eliminado de la array . 
Entrada: arr[] = {2, 4, 7, 8, 9, 11} 
Salida: 4 7 9 11 
Explicación: 
La array contiene 2 valores de datos de fibonacci 2 y 8. 
Estos valores se han eliminado de la array. 
 

Enfoque: la idea es usar hashing para precalcular y almacenar los números de Fibonacci , y luego verificar si un Node contiene un valor de Fibonacci en tiempo O (1).
 

1. Recorra la array y verifique si el número actual es un Fibonacci o no usa el hash precalculado.
2. Si es así, cambie a la izquierda todos los elementos que le siguen para eliminar este número de Fibonacci y disminuir el valor de la longitud de la array.
3. Repita los pasos anteriores para todos los elementos de la array.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to remove all the
// fibonacci numbers from the
// given array
 
#include <bits/stdc++.h>
using namespace std;
 
const int sz = 1e3;
 
// Set to store all the Fibonacci numbers
set<int> fib;
 
// Function to generate Fibonacci numbers using
// Dynamic Programming and create hash table
// to check Fibonacci numbers
void fibonacci()
{
    // Storing the first two Fibonacci
    // numbers in the set
    int prev = 0, curr = 1, len = 2;
    fib.insert(prev);
    fib.insert(curr);
 
    // Compute the remaining Fibonacci numbers
    // until the max size and store them
    // in the set
    while (len <= sz) {
        int temp = curr + prev;
        fib.insert(temp);
        prev = curr;
        curr = temp;
        len++;
    }
}
 
// Function to print the elements of the array
void printArray(int arr[], int len)
{
    for (int i = 0; i < len; i++) {
        cout << arr[i] << ' ';
    }
}
 
// Function to remove all the Fibonacci numbers
// from the array
void removeFibonacci(int arr[], int len)
{
    // Creating a set containing
    // all the fibonacci numbers
    fibonacci();
 
    // Traverse the array
    for (int i = 0; i < len; i++) {
 
        // If the current element is fibonacci
        if (fib.find(arr[i]) != fib.end()) {
 
            // Shift all the elements on the
            // right of it to the left
            for (int j = i; j < len; j++) {
                arr[j] = arr[j + 1];
            }
 
            // Decrease the loop counter by 1
            // to check the shifted element
            i--;
 
            // Decrease the length
            len--;
        }
    }
 
    // Print the updated array
    printArray(arr, len);
}
 
// Driver code
int main()
{
    int arr[] = { 4, 6, 5, 3, 8, 7,
                  10, 11, 14, 15 };
 
    int len = sizeof(arr) / sizeof(int);
 
    removeFibonacci(arr, len);
 
    return 0;
}

// Java program to remove all the
// fibonacci numbers from the
// given array
import java.util.*;
 
class GFG{
  
static int sz = (int) 1e3;
  
// Set to store all the Fibonacci numbers
static HashSet<Integer> fib = new HashSet<Integer>();
  
// Function to generate Fibonacci numbers using
// Dynamic Programming and create hash table
// to check Fibonacci numbers
static void fibonacci()
{
    // Storing the first two Fibonacci
    // numbers in the set
    int prev = 0, curr = 1, len = 2;
    fib.add(prev);
    fib.add(curr);
  
    // Compute the remaining Fibonacci numbers
    // until the max size and store them
    // in the set
    while (len <= sz) {
        int temp = curr + prev;
        fib.add(temp);
        prev = curr;
        curr = temp;
        len++;
    }
}
  
// Function to print the elements of the array
static void printArray(int arr[], int len)
{
    for (int i = 0; i < len; i++) {
        System.out.print(arr[i] +" ");
    }
}
  
// Function to remove all the Fibonacci numbers
// from the array
static void removeFibonacci(int arr[], int len)
{
    // Creating a set containing
    // all the fibonacci numbers
    fibonacci();
  
    // Traverse the array
    for (int i = 0; i < len; i++) {
  
        // If the current element is fibonacci
        if (fib.contains(arr[i])) {
  
            // Shift all the elements on the
            // right of it to the left
            for (int j = i; j < len - 1; j++) {
                arr[j] = arr[j + 1];
            }
  
            // Decrease the loop counter by 1
            // to check the shifted element
            i--;
  
            // Decrease the length
            len--;
        }
    }
  
    // Print the updated array
    printArray(arr, len);
}
  
// Driver code
public static void main(String[] args)
{
    int arr[] = { 4, 6, 5, 3, 8, 7,
                  10, 11, 14, 15 };
  
    int len = arr.length;
    removeFibonacci(arr, len);
}
}
 
// This code is contributed by 29AjayKumar

# Python 3 program to remove all the
# fibonacci numbers from the
# given array
 
sz = 1000
 
# Set to store all the Fibonacci numbers
fib = set()
 
# Function to generate Fibonacci numbers using
# Dynamic Programming and create hash table
# to check Fibonacci numbers
def fibonacci():
 
    # Storing the first two Fibonacci
    # numbers in the set
    prev , curr , length = 0 , 1, 2
    fib.add(prev)
    fib.add(curr)
 
    # Compute the remaining Fibonacci numbers
    # until the max size and store them
    # in the set
    while (length <= sz):
        temp = curr + prev
        fib.add(temp)
        prev = curr
        curr = temp
        length += 1
 
# Function to print the elements of the array
def printArray( arr, length):
 
    for i in range(length):
        print(arr[i],end=" ")
         
# Function to remove all the Fibonacci numbers
# from the array
def removeFibonacci( arr, length):
 
    # Creating a set containing
    # all the fibonacci numbers
    fibonacci()
 
    # Traverse the array
    for i in fib:
        if i in arr:
            arr.remove(i)
            length -= 1
 
    # Print the updated array
    printArray(arr, length)
 
# Driver code
if __name__ == "__main__":
     
    arr = [ 4, 6, 5, 3, 8, 7,
                10, 11, 14, 15 ]
 
    length = len(arr)
    removeFibonacci(arr, length)
 
# This code is contributed by chitranayal

// C# program to remove all the
// fibonacci numbers from the
// given array
using System;
using System.Collections.Generic;
 
class GFG{
   
static int sz = (int) 1e3;
   
// Set to store all the Fibonacci numbers
static HashSet<int> fib = new HashSet<int>();
   
// Function to generate Fibonacci numbers using
// Dynamic Programming and create hash table
// to check Fibonacci numbers
static void fibonacci()
{
    // Storing the first two Fibonacci
    // numbers in the set
    int prev = 0, curr = 1, len = 2;
    fib.Add(prev);
    fib.Add(curr);
   
    // Compute the remaining Fibonacci numbers
    // until the max size and store them
    // in the set
    while (len <= sz) {
        int temp = curr + prev;
        fib.Add(temp);
        prev = curr;
        curr = temp;
        len++;
    }
}
   
// Function to print the elements of the array
static void printArray(int []arr, int len)
{
    for (int i = 0; i < len; i++) {
        Console.Write(arr[i] +" ");
    }
}
   
// Function to remove all the Fibonacci numbers
// from the array
static void removeFibonacci(int []arr, int len)
{
    // Creating a set containing
    // all the fibonacci numbers
    fibonacci();
   
    // Traverse the array
    for (int i = 0; i < len; i++) {
   
        // If the current element is fibonacci
        if (fib.Contains(arr[i])) {
   
            // Shift all the elements on the
            // right of it to the left
            for (int j = i; j < len - 1; j++) {
                arr[j] = arr[j + 1];
            }
   
            // Decrease the loop counter by 1
            // to check the shifted element
            i--;
   
            // Decrease the length
            len--;
        }
    }
   
    // Print the updated array
    printArray(arr, len);
}
   
// Driver code
public static void Main(String[] args)
{
    int []arr = { 4, 6, 5, 3, 8, 7,
                  10, 11, 14, 15 };
   
    int len = arr.Length;
    removeFibonacci(arr, len);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program to remove all the
// fibonacci numbers from the
// given array
 
let sz = 1e3;
    
// Set to store all the Fibonacci numbers
let fib = new Set();
    
// Function to generate Fibonacci numbers using
// Dynamic Programming and create hash table
// to check Fibonacci numbers
function fibonacci()
{
    // Storing the first two Fibonacci
    // numbers in the set
    let prev = 0, curr = 1, len = 2;
    fib.add(prev);
    fib.add(curr);
    
    // Compute the remaining Fibonacci numbers
    // until the max size and store them
    // in the set
    while (len <= sz) {
        let temp = curr + prev;
        fib.add(temp);
        prev = curr;
        curr = temp;
        len++;
    }
}
    
// Function to print the elements of the array
function printArray(arr, len)
{
    for (let i = 0; i < len; i++) {
        document.write(arr[i] +" ");
    }
}
    
// Function to remove all the Fibonacci numbers
// from the array
function removeFibonacci(arr, len)
{
    // Creating a set containing
    // all the fibonacci numbers
    fibonacci();
    
    // Traverse the array
    for (let i = 0; i < len; i++) {
    
        // If the current element is fibonacci
        if (fib.has(arr[i])) {
    
            // Shift all the elements on the
            // right of it to the left
            for (let j = i; j < len - 1; j++) {
                arr[j] = arr[j + 1];
            }
    
            // Decrease the loop counter by 1
            // to check the shifted element
            i--;
    
            // Decrease the length
            len--;
        }
    }
    
    // Print the updated array
    printArray(arr, len);
}
 
// Driver code
     
      let arr = [ 4, 6, 5, 3, 8, 7,
                  10, 11, 14, 15 ];
    
    let len = arr.length;
    removeFibonacci(arr, len);
 
// This code is contributed by sanjoy_62.
</script>

4 6 7 10 11 14 15