Dada una array arr[] que contiene N elementos, la tarea es verificar si la suma de los elementos de Fibonacci de la array es un número de Fibonacci o no.
Ejemplos:
Entrada: arr[] = {2, 3, 7, 11}
Salida: Sí
Explicación:
Como hay dos números de Fibonacci en la array, es decir, 2 y 3.
Entonces, la suma de los números de Fibonacci es 2 + 3 = 5 y 5 es también un número de Fibonacci.
Entrada: arr[] = {1, 2, 3}
Salida: No
Enfoque: La idea es usar hash para precalcular y almacenar los Nodes de Fibonacci hasta el número máximo para que la verificación sea fácil y eficiente (en tiempo O(1)).
Después del cálculo previo, itere sobre todos los elementos de la array. Si el número es un número de Fibonacci, súmalo a la suma. Y finalmente, comprueba si la suma es un número de Fibonacci o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check whether the
// sum of fibonacci elements of the
// array is a Fibonacci number or not
#include <bits/stdc++.h>
#define ll long long int
#define MAX 100005
using namespace std;
// Hash to store the Fibonacci
// numbers up to Max
set<int> fibonacci;
// Function to create the hash table
// to check Fibonacci numbers
void createHash()
{
// Inserting the first two Fibonacci
// numbers into the hash
int prev = 0, curr = 1;
fibonacci.insert(prev);
fibonacci.insert(curr);
// Add the remaining Fibonacci numbers
// based on the previous two numbers
while (curr <= MAX) {
int temp = curr + prev;
fibonacci.insert(temp);
prev = curr;
curr = temp;
}
}
// Function to check if the sum of
// Fibonacci numbers is Fibonacci or not
bool checkArray(int arr[], int n)
{
// Find the sum of
// all Fibonacci numbers
ll sum = 0;
// Iterating through the array
for (int i = 0; i < n; i++)
if (fibonacci.find(arr[i])
!= fibonacci.end())
sum += arr[i];
// If the sum is Fibonacci
// then return true
if (fibonacci.find(sum)
!= fibonacci.end())
return true;
return false;
}
// Driver code
int main()
{
// array of elements
int arr[] = { 1, 2, 4, 8, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
// Creating a set containing
// all fibonacci numbers
createHash();
if (checkArray(arr, n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program to check whether the
// sum of fibonacci elements of the
// array is a Fibonacci number or not
import java.util.*;
class GFG{
static final int MAX = 100005;
// Hash to store the Fibonacci
// numbers up to Max
static HashSet<Integer> fibonacci = new HashSet<Integer>();
// Function to create the hash table
// to check Fibonacci numbers
static void createHash()
{
// Inserting the first two Fibonacci
// numbers into the hash
int prev = 0, curr = 1;
fibonacci.add(prev);
fibonacci.add(curr);
// Add the remaining Fibonacci numbers
// based on the previous two numbers
while (curr <= MAX) {
int temp = curr + prev;
fibonacci.add(temp);
prev = curr;
curr = temp;
}
}
// Function to check if the sum of
// Fibonacci numbers is Fibonacci or not
static boolean checkArray(int arr[], int n)
{
// Find the sum of
// all Fibonacci numbers
int sum = 0;
// Iterating through the array
for (int i = 0; i < n; i++)
if (fibonacci.contains(arr[i]))
sum += arr[i];
// If the sum is Fibonacci
// then return true
if (fibonacci.contains(sum))
return true;
return false;
}
// Driver code
public static void main(String[] args)
{
// array of elements
int arr[] = { 1, 2, 4, 8, 2 };
int n = arr.length;
// Creating a set containing
// all fibonacci numbers
createHash();
if (checkArray(arr, n))
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python 3 program to check whether the
# sum of fibonacci elements of the
# array is a Fibonacci number or not
MAX = 100005
# Hash to store the Fibonacci
# numbers up to Max
fibonacci = set()
# Function to create the hash table
# to check Fibonacci numbers
def createHash():
global fibonacci
# Inserting the first two Fibonacci
# numbers into the hash
prev , curr = 0, 1
fibonacci.add(prev)
fibonacci.add(curr)
# Add the remaining Fibonacci numbers
# based on the previous two numbers
while (curr <= MAX):
temp = curr + prev
if temp <= MAX:
fibonacci.add(temp)
prev = curr
curr = temp
# Function to check if the sum of
# Fibonacci numbers is Fibonacci or not
def checkArray(arr, n):
# Find the sum of
# all Fibonacci numbers
sum = 0
# Iterating through the array
for i in range( n ):
if (arr[i] in fibonacci):
sum += arr[i]
# If the sum is Fibonacci
# then return true
if (sum in fibonacci):
return True
return False
# Driver code
if __name__ == "__main__":
# array of elements
arr = [ 1, 2, 4, 8, 2 ]
n = len(arr)
# Creating a set containing
# all fibonacci numbers
createHash()
if (checkArray(arr, n)):
print("Yes")
else:
print("No")
# This code is contributed by chitranayal
C#
// C# program to check whether the
// sum of fibonacci elements of the
// array is a Fibonacci number or not
using System;
using System.Collections.Generic;
class GFG{
static readonly int MAX = 100005;
// Hash to store the Fibonacci
// numbers up to Max
static HashSet<int> fibonacci = new HashSet<int>();
// Function to create the hash table
// to check Fibonacci numbers
static void createHash()
{
// Inserting the first two Fibonacci
// numbers into the hash
int prev = 0, curr = 1;
fibonacci.Add(prev);
fibonacci.Add(curr);
// Add the remaining Fibonacci numbers
// based on the previous two numbers
while (curr <= MAX) {
int temp = curr + prev;
fibonacci.Add(temp);
prev = curr;
curr = temp;
}
}
// Function to check if the sum of
// Fibonacci numbers is Fibonacci or not
static bool checkArray(int []arr, int n)
{
// Find the sum of
// all Fibonacci numbers
int sum = 0;
// Iterating through the array
for (int i = 0; i < n; i++)
if (fibonacci.Contains(arr[i]))
sum += arr[i];
// If the sum is Fibonacci
// then return true
if (fibonacci.Contains(sum))
return true;
return false;
}
// Driver code
public static void Main(String[] args)
{
// array of elements
int []arr = { 1, 2, 4, 8, 2 };
int n = arr.Length;
// Creating a set containing
// all fibonacci numbers
createHash();
if (checkArray(arr, n))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript program to check whether the
// sum of fibonacci elements of the
// array is a Fibonacci number or not
let MAX = 100005;
// Hash to store the Fibonacci
// numbers up to Max
let fibonacci = new Set();
// Function to create the hash table
// to check Fibonacci numbers
function createHash()
{
// Inserting the first two Fibonacci
// numbers into the hash
let prev = 0, curr = 1;
fibonacci.add(prev);
fibonacci.add(curr);
// Add the remaining Fibonacci numbers
// based on the previous two numbers
while (curr <= MAX) {
let temp = curr + prev;
fibonacci.add(temp);
prev = curr;
curr = temp;
}
}
// Function to check if the sum of
// Fibonacci numbers is Fibonacci or not
function checkArray(arr, n)
{
// Find the sum of
// all Fibonacci numbers
let sum = 0;
// Iterating through the array
for (let i = 0; i < n; i++)
if (fibonacci.has(arr[i]))
sum += arr[i];
// If the sum is Fibonacci
// then return true
if (fibonacci.has(sum))
return true;
return false;
}
// Driver code
// array of elements
let arr = [ 1, 2, 4, 8, 2 ];
let n = arr.length;
// Creating a set containing
// all fibonacci numbers
createHash();
if (checkArray(arr, n))
document.write("Yes");
else
document.write("No");
// This code is contributed by sanjoy_62.
</script>
Producción:
Yes
Complejidad de tiempo: O (nlogn), donde n representa el tamaño de la array dada.
Espacio auxiliar: O(n), donde n representa el tamaño de la array dada.
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