Remove all the fibonacci numbers from the given array

0 0 7 minutes read

Given an array arr[] of N integers, the task is to remove all the fibonacci numbers present in the array.
Examples:

Input: arr[] = {4, 6, 5, 3, 8, 7, 10, 11, 14, 15}
Output: 4 6 7 10 11 14 15
Explanation:
The array contains 3 fibonacci data values 5, 3 and 8.
These values have been removed from the array.
Input: arr[] = {2, 4, 7, 8, 9, 11}
Output: 4 7 9 11
Explanation:
The array contains 2 fibonacci data values 2 and 8.
These values have been removed from the array.

Approach: The idea is to use hashing to precompute and store the Fibonacci numbers, and then check if a node contains a Fibonacci value in O(1) time.

Traverse the array and check if the current number is a Fibonacci or not using the precomputed hash.
If it is, then left shift all the elements after it to remove this Fibonacci number and decrease the value of the array length.
Repeat the above steps for all the elements of the array.

Below is the implementation of the above approach:

C++

// 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

// 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

Python3

# 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#

// 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

Javascript

<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>

Output:

4 6 7 10 11 14 15

Time Complexity: O(n²)
Auxiliary Space: O(n), where n is the size of the given array.

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 zambiatek!