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> |
4 6 7 10 11 14 15
Time Complexity: O(n2)
Auxiliary Space: O(n), where n is the size of the given array.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!