Largest and smallest Fibonacci numbers in an Array

0 0 11 minutes read

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>

Output

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*n² + 4) or (5*n² – 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);
    }
}

Output

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

Output

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)

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!