Dada una array arr[] de N enteros positivos, la tarea es encontrar los elementos de Fibonacci mínimos (más pequeños) y máximos (más grandes) en la array dada.
Ejemplos:
Entrada: arr[] = 1, 2, 3, 4, 5, 6, 7
Salida: 1, 5
Explicación:
la array contiene 4 valores de fibonacci 1, 2, 3 y 5.
Por lo tanto, el máximo es 5 y el mínimo es 1.
Entrada: arr[] = 13, 3, 15, 6, 8, 11
Salida: 3, 13
Explicación:
La array contiene 3 valores de fibonacci 13, 3 y 8.
Por lo tanto, el máximo es 13 y el mínimo es 3.
Enfoque: este enfoque es similar a encontrar el elemento mínimo y máximo en una array. Recorra la array una por una y verifique si es un número de Fibonacci o no. Si es así, encuentre el máximo y el mínimo entre tales números.
Para comprobar si el número es un número de Fibonacci o no de manera óptima O(1), genere todos los números de Fibonacci hasta el elemento máximo de la array mediante programación dinámica y almacénelos en una tabla hash.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
1, 5
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA