Largest and smallest Fibonacci numbers in an Array
Given an array arr[] of N positive integers, the task is to find the minimum (smallest) and maximum (largest) Fibonacci elements in the given array.
Examples:
Input: arr[] = 1, 2, 3, 4, 5, 6, 7
Output: 1, 5
Explanation :
The array contains 4 fibonacci values 1, 2, 3 and 5.
Hence, the maximum is 5 and the minimum is 1.
Input: arr[] = 13, 3, 15, 6, 8, 11
Output:3, 13
Explanation:
The array contains 3 fibonacci values 13, 3 and 8.
Hence, the maximum is 13 and the minimum is 3.
Approach 1:
This approach is similar to finding the minimum and maximum element in an array. Traverse the array one by one, and check if it is a Fibonacci number or not. If it is, then find the maximum and minimum among such numbers.
Inorder to check if the number is a Fibonacci number or not optimally O(1), generate all Fibonacci numbers up to the maximum element of the array using dynamic programming and store them in a hash table.
Below is the implementation of above approach:
C++
// C++ program to find minimum and maximum // fibonacci number in given array #include <bits/stdc++.h> using namespace std; // Function to create hash table // to check Fibonacci numbers void createHash(set< int >& hash, int maxElement) { // Insert initial two numbers // in the hash table int prev = 0, curr = 1; hash.insert(prev); hash.insert(curr); while (curr <= maxElement) { // Sum of previous two numbers int temp = curr + prev; hash.insert(temp); // Update the variable each time prev = curr; curr = temp; } } // Function to find minimum and maximum // fibonacci number in given array void fibonacci( int arr[], int n) { // Find maximum value in the array int max_val = *max_element( arr, arr + n); // Creating a set containing // all Fibonacci numbers up to // maximum value in the array set< int > hash; createHash(hash, max_val); // For storing the Minimum // and Maximum Fibonacci number int minimum = INT_MAX; int maximum = INT_MIN; for ( int i = 0; i < n; i++) { // Check if current element // is a fibonacci number if (hash.find(arr[i]) != hash.end()) { // Update the maximum and // minimum accordingly minimum = min(minimum, arr[i]); maximum = max(maximum, arr[i]); } } cout << minimum << ", " << maximum << endl; } // Driver code int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; int n = sizeof (arr) / sizeof (arr[0]); fibonacci(arr, n); return 0; } |
Java
// Java program to find minimum and maximum // fibonacci number in given array import java.util.*; class GFG{ // Function to create hash table // to check Fibonacci numbers static void createHash(HashSet<Integer> hash, int maxElement) { // Insert initial two numbers // in the hash table int prev = 0 , curr = 1 ; hash.add(prev); hash.add(curr); while (curr <= maxElement) { // Sum of previous two numbers int temp = curr + prev; hash.add(temp); // Update the variable each time prev = curr; curr = temp; } } // Function to find minimum and maximum // fibonacci number in given array static void fibonacci( int arr[], int n) { // Find maximum value in the array int max_val= Arrays.stream(arr).max().getAsInt(); // Creating a set containing // all Fibonacci numbers up to // maximum value in the array HashSet<Integer> hash = new HashSet<Integer>(); createHash(hash, max_val); // For storing the Minimum // and Maximum Fibonacci number int minimum = Integer.MAX_VALUE; int maximum = Integer.MIN_VALUE; for ( int i = 0 ; i < n; i++) { // Check if current element // is a fibonacci number if (hash.contains(arr[i])) { // Update the maximum and // minimum accordingly minimum = Math.min(minimum, arr[i]); maximum = Math.max(maximum, arr[i]); } } System.out.print(minimum+ ", " + maximum + "\n" ); } // Driver code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 }; int n = arr.length; fibonacci(arr, n); } } // This code is contributed by sapnasingh4991 |
Python3
# Python 3 program to find minimum and maximum # fibonacci number in given array import sys # Function to create hash table # to check Fibonacci numbers def createHash( hash , maxElement): # Insert initial two numbers # in the hash table prev = 0 curr = 1 hash .add(prev) hash .add(curr) while (curr < = maxElement): # Sum of previous two numbers temp = curr + prev hash .add(temp) # Update the variable each time prev = curr curr = temp # Function to find minimum and maximum # fibonacci number in given array def fibonacci(arr, n): # Find maximum value in the array max_val = max (arr) # Creating a set containing # all Fibonacci numbers up to # maximum value in the array hash = set () createHash( hash , max_val) # For storing the Minimum # and Maximum Fibonacci number minimum = sys.maxsize maximum = - sys.maxsize - 1 for i in range (n): # Check if current element # is a fibonacci number if (arr[i] in hash ): # Update the maximum and # minimum accordingly minimum = min (minimum, arr[i]) maximum = max (maximum, arr[i]) print (minimum,end = ", " ) print (maximum) # Driver code if __name__ = = '__main__' : arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] n = len (arr) fibonacci(arr, n) # This code is contributed by Surendra_Gangwar |
C#
// C# program to find minimum and maximum // fibonacci number in given array using System; using System.Linq; using System.Collections.Generic; class GFG{ // Function to create hash table // to check Fibonacci numbers static void createHash(HashSet< int > hash, int maxElement) { // Insert initial two numbers // in the hash table int prev = 0, curr = 1; hash.Add(prev); hash.Add(curr); while (curr <= maxElement) { // Sum of previous two numbers int temp = curr + prev; hash.Add(temp); // Update the variable each time prev = curr; curr = temp; } } // Function to find minimum and maximum // fibonacci number in given array static void fibonacci( int []arr, int n) { // Find maximum value in the array int max_val= arr.Max(); // Creating a set containing // all Fibonacci numbers up to // maximum value in the array HashSet< int > hash = new HashSet< int >(); createHash(hash, max_val); // For storing the Minimum // and Maximum Fibonacci number int minimum = int .MaxValue; int maximum = int .MinValue; for ( int i = 0; i < n; i++) { // Check if current element // is a fibonacci number if (hash.Contains(arr[i])) { // Update the maximum and // minimum accordingly minimum = Math.Min(minimum, arr[i]); maximum = Math.Max(maximum, arr[i]); } } Console.Write(minimum+ ", " + maximum + "\n" ); } // Driver code public static void Main(String[] args) { int []arr = { 1, 2, 3, 4, 5, 6, 7 }; int n = arr.Length; fibonacci(arr, n); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program to find minimum and maximum // fibonacci number in given array // Function to create hash table // to check Fibonacci numbers function createHash(hash, maxElement) { // Insert initial two numbers // in the hash table let prev = 0, curr = 1; hash.add(prev); hash.add(curr); while (curr <= maxElement) { // Sum of previous two numbers let temp = curr + prev; hash.add(temp); // Update the variable each time prev = curr; curr = temp; } } // Function to find minimum and maximum // fibonacci number in given array function fibonacci(arr, n) { // Find maximum value in the array let max_val= Math.max(...arr); // Creating a set containing // all Fibonacci numbers up to // maximum value in the array let hash = new Set(); createHash(hash, max_val); // For storing the Minimum // and Maximum Fibonacci number let minimum = Number.MAX_VALUE; let maximum = Number.MIN_VALUE; for (let i = 0; i < n; i++) { // Check if current element // is a fibonacci number if (hash.has(arr[i])) { // Update the maximum and // minimum accordingly minimum = Math.min(minimum, arr[i]); maximum = Math.max(maximum, arr[i]); } } document.write(minimum+ ", " + maximum + "<br/>" ); } // Driver code let arr = [ 1, 2, 3, 4, 5, 6, 7 ]; let n = arr.length; fibonacci(arr, n); // This code is contributed by sanjoy_62. </script> |
1, 5
Time Complexity: O(n + log(m)), where n is the size of the given array and m is the maximum element in the array.
Auxiliary Space: O(n)
Approach 2:
This approach use the below formula to check if the current number is Fibonacci number or not:
A number is Fibonacci if and only if one or both of (5*n2 + 4) or (5*n2 – 4) is a perfect square (Source: Wiki).
Steps:
To find the largest and smallest Fibonacci numbers in an array, we do the following steps:
- First initialize max and min Fibonacci number as INT_MIN and INT_MAX respectively.
- Then we iterate array and for each element check if the element is Fibonacci number or not.
- In each iteration:
- If the element is Fibonacci number then compare it with max and min Fibonacci numbers and as per its value change max or min.
- And at the end print the max and min Fibonacci number.
Below is the implementation of the above approach:
C++
// C++ program to find minimum and maximum // fibonacci number in given array #include <bits/stdc++.h> using namespace std; // A utility function that returns true if x is perfect // square bool isPerfectSquare( int x) { int s = sqrt (x); return (s * s == x); } // Returns true if n is a Fibonacci Number, else false bool isFibonacci( int n) { // n is Fibonacci if one of 5*n*n + 4 or 5*n*n - 4 or // both is a perfect square return isPerfectSquare(5 * n * n + 4) || isPerfectSquare(5 * n * n - 4); } // Function to find minimum and maximum // fibonacci number in given array void fibonacci( int arr[], int n) { // For storing the Minimum // and Maximum Fibonacci number int minimum = INT_MAX; int maximum = INT_MIN; for ( int i = 0; i < n; i++) { // Check if current element // is a fibonacci number if (isFibonacci(arr[i])) { // Update the maximum and minimum accordingly minimum = min(minimum, arr[i]); maximum = max(maximum, arr[i]); } } cout << minimum << ", " << maximum << endl; } // Driver code int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; int n = sizeof (arr) / sizeof (arr[0]); fibonacci(arr, n); return 0; } // This code is contributed by Susobhan Akhuli |
Java
import java.util.*; public class FibonacciMinMax { // A utility function that returns true if x is a perfect square static boolean isPerfectSquare( int x) { int s = ( int ) Math.sqrt(x); return (s * s == x); } // Returns true if n is a Fibonacci Number, else false static boolean isFibonacci( int n) { // n is Fibonacci if one of 5*n*n + 4 or 5*n*n - 4 or both is a perfect square return isPerfectSquare( 5 * n * n + 4 ) || isPerfectSquare( 5 * n * n - 4 ); } // Function to find minimum and maximum Fibonacci numbers in the given array static void fibonacci( int [] arr) { int minimum = Integer.MAX_VALUE; int maximum = Integer.MIN_VALUE; for ( int i = 0 ; i < arr.length; i++) { // Check if the current element is a Fibonacci number if (isFibonacci(arr[i])) { // Update the maximum and minimum accordingly minimum = Math.min(minimum, arr[i]); maximum = Math.max(maximum, arr[i]); } } System.out.println(minimum + ", " + maximum); } // Driver code public static void main(String[] args) { int [] arr = { 1 , 2 , 3 , 4 , 5 , 6 , 7 }; fibonacci(arr); } } |
Python3
import math # A utility function that returns true if x is a perfect square def isPerfectSquare(x): s = int (math.sqrt(x)) return s * s = = x # Returns true if n is a Fibonacci Number, else false def isFibonacci(n): # n is Fibonacci if one of 5*n*n + 4 or 5*n*n - 4 or both is a perfect square return isPerfectSquare( 5 * n * n + 4 ) or isPerfectSquare( 5 * n * n - 4 ) # Function to find minimum and maximum Fibonacci number in the given array def fibonacci(arr): # For storing the Minimum and Maximum Fibonacci number minimum = float ( 'inf' ) maximum = float ( '-inf' ) for num in arr: # Check if the current element is a Fibonacci number if isFibonacci(num): # Update the maximum and minimum accordingly minimum = min (minimum, num) maximum = max (maximum, num) print (f " {minimum}, {maximum}" ) # Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] n = len (arr) fibonacci(arr) |
C#
using System; class Program { // A utility function that returns true if x is a perfect square static bool IsPerfectSquare( int x) { int s = ( int )Math.Sqrt(x); return (s * s == x); } // Returns true if n is a Fibonacci Number, else false static bool IsFibonacci( int n) { // n is Fibonacci if one of 5*n*n + 4 or 5*n*n - 4 or both is a perfect square return IsPerfectSquare(5 * n * n + 4) || IsPerfectSquare(5 * n * n - 4); } // Function to find the minimum and maximum Fibonacci numbers in a given array static void Fibonacci( int [] arr) { int minimum = int .MaxValue; int maximum = int .MinValue; foreach ( int num in arr) { if (IsFibonacci(num)) { minimum = Math.Min(minimum, num); maximum = Math.Max(maximum, num); } } Console.WriteLine(minimum + ", " + maximum); } // Driver code static void Main( string [] args) { int [] arr = { 1, 2, 3, 4, 5, 6, 7 }; Fibonacci(arr); } } |
Javascript
// JavaScript function to check if a number is a perfect square function isPerfectSquare(x) { const s = Math.sqrt(x); return s * s === x; } // JavaScript function to check if a number is a Fibonacci number function isFibonacci(n) { // n is Fibonacci if 5*n*n + 4 or 5*n*n - 4 is a perfect square return isPerfectSquare(5 * n * n + 4) || isPerfectSquare(5 * n * n - 4); } // Function to find the minimum and maximum Fibonacci number in a given array function fibonacci(arr) { // Initialize variables to store the minimum and maximum Fibonacci numbers let minimum = Infinity; let maximum = -Infinity; for (let i = 0; i < arr.length; i++) { // Check if the current element is a Fibonacci number if (isFibonacci(arr[i])) { // Update the minimum and maximum accordingly minimum = Math.min(minimum, arr[i]); maximum = Math.max(maximum, arr[i]); } } console.log(`${minimum}, ${maximum}`); } // Driver code function main() { const arr = [1, 2, 3, 4, 5, 6, 7]; fibonacci(arr); } // Call the main function to execute the code main(); |
1, 5
Time Complexity: O(N*log(M)), where N is the size of the given array and M is the maximum element in the array.
Auxiliary Space: O(1)
Approach 3:
This approach is one of the optimal approach to find the largest and smallest Fibonacci numbers in an array.
Steps:
To find the largest and smallest Fibonacci numbers in an array, we do the following steps:
- First initialize max and min Fibonacci number as INT_MIN and INT_MAX respectively.
- Then we iterate array and for each element check if the element is Fibonacci number or not.
- To check if the element is Fibonacci number or not we:
- First check if the number is 0 or 1, then return true.
- Then till the number comes do while loop.
- In each iteration:
- First calculate fibonacci of that iteration.
- Then check if it matches with given number or not.
- If matches, return true.
- If the value goes beyond, given number then return false.
- Otherwise continue.
- In each iteration:
- If the element is Fibonacci number then compare it with max and min Fibonacci numbers and as per its value change max or min.
- And at the end print the max and min Fibonacci number.
Below
C++
// C++ program to find minimum and maximum // fibonacci number in given array #include <bits/stdc++.h> using namespace std; // Function to check Fibonacci number bool isFibonacci( int N) { if (N == 0 || N == 1) return true ; int a = 0, b = 1, c; while ( true ) { c = a + b; a = b; b = c; if (c == N) return true ; else if (c >= N) { return false ; } } } // Function to find minimum and maximum // fibonacci number in given array void fibonacci( int arr[], int n) { // For storing the Minimum // and Maximum Fibonacci number int minimum = INT_MAX; int maximum = INT_MIN; for ( int i = 0; i < n; i++) { // Check if current element // is a fibonacci number if (isFibonacci(arr[i])) { // Update the maximum and minimum accordingly minimum = min(minimum, arr[i]); maximum = max(maximum, arr[i]); } } cout << minimum << ", " << maximum << endl; } // Driver code int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; int n = sizeof (arr) / sizeof (arr[0]); fibonacci(arr, n); return 0; } // This code is contributed by Susobhan Akhuli |
Java
import java.util.Arrays; public class FibonacciMinMax { // Function to check if a number is a Fibonacci number public static boolean isFibonacci( int N) { if (N == 0 || N == 1 ) { return true ; } int a = 0 , b = 1 , c; while ( true ) { c = a + b; a = b; b = c; if (c == N) { return true ; } else if (c >= N) { return false ; } } } // Function to find the minimum and maximum Fibonacci number in the given array public static void fibonacci( int [] arr) { int minimum = Integer.MAX_VALUE; int maximum = Integer.MIN_VALUE; for ( int i = 0 ; i < arr.length; i++) { if (isFibonacci(arr[i])) { minimum = Math.min(minimum, arr[i]); maximum = Math.max(maximum, arr[i]); } } System.out.println( "Minimum: " + minimum + ", Maximum: " + maximum); } public static void main(String[] args) { int [] arr = { 1 , 2 , 3 , 4 , 5 , 6 , 7 }; fibonacci(arr); } } |
Python3
def is_fibonacci(N): if N = = 0 or N = = 1 : return True a, b = 0 , 1 while True : c = a + b a = b b = c if c = = N: return True elif c > = N: return False def find_fibonacci_min_max(arr): minimum = float ( 'inf' ) # Initialize the minimum as positive infinity maximum = float ( '-inf' ) # Initialize the maximum as negative infinity for num in arr: if is_fibonacci(num): # Check if the current number is a Fibonacci number minimum = min (minimum, num) # Update the minimum if needed maximum = max (maximum, num) # Update the maximum if needed return minimum, maximum arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] minimum, maximum = find_fibonacci_min_max(arr) print (f "{minimum}, {maximum}" ) |
C#
using System; class Program { // Function to check Fibonacci number static bool IsFibonacci( int N) { if (N == 0 || N == 1) return true ; int a = 0, b = 1, c; while ( true ) { c = a + b; a = b; b = c; if (c == N) return true ; else if (c >= N) return false ; } } // Function to find minimum and maximum // Fibonacci number in given array static void Fibonacci( int [] arr, int n) { // For storing the Minimum // and Maximum Fibonacci number int minimum = int .MaxValue; int maximum = int .MinValue; for ( int i = 0; i < n; i++) { // Check if the current element is a Fibonacci // number if (IsFibonacci(arr[i])) { // Update the maximum and minimum // accordingly minimum = Math.Min(minimum, arr[i]); maximum = Math.Max(maximum, arr[i]); } } Console.WriteLine(minimum + ", " + maximum); } // Driver code static void Main() { int [] arr = { 1, 2, 3, 4, 5, 6, 7 }; int n = arr.Length; Fibonacci(arr, n); } } |
Javascript
// Function to check if a number is a Fibonacci number function isFibonacci(N) { if (N === 0 || N === 1) { return true ; } let a = 0, b = 1, c; while ( true ) { c = a + b; a = b; b = c; if (c === N) { return true ; } else if (c >= N) { return false ; } } } // Function to find the minimum and maximum Fibonacci numbers in the given array function fibonacci(arr) { // For storing the minimum and maximum Fibonacci numbers let minimum = Infinity; let maximum = -Infinity; for (let i = 0; i < arr.length; i++) { // Check if the current element is a Fibonacci number if (isFibonacci(arr[i])) { // Update the minimum and maximum accordingly minimum = Math.min(minimum, arr[i]); maximum = Math.max(maximum, arr[i]); } } console.log(minimum + ', ' + maximum); } // Driver code const arr = [1, 2, 3, 4, 5, 6, 7]; fibonacci(arr); |
1, 5
Time Complexity: O(N*log(M)), where N is the size of the given array and M is the maximum element in the array.
Auxiliary Space: O(1)