Dada una array arr[] , la tarea es contar el número de pares de Fibonacci consecutivos en esta array.
Ejemplos:
Entrada: arr[] = { 3, 5, 6, 11 }
Salida: 1
El único par es (3, 5) que es un par de Fibonacci consecutivo en la array
Entrada: arr[] = { 3, 5, 8, 11 }
Salida: 2
Hay dos pares (3, 5) y (5, 8) en la array, que es un par de Fibonacci consecutivo.
Acercarse:
- Encuentra todos los pares de la array .
- Para cada par,
- Encuentre el mínimo y el máximo del par.
- Encuentre el siguiente número de fibonacci consecutivo después del elemento_mínimo y verifique que sea igual al máximo del par.
- Si el siguiente número de Fibonacci consecutivo es igual al elemento máximo del par, incremente el conteo en 1.
- Devuelva el conteo total como el número requerido de pares.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count the
// consecutive fibonacci pairs in the array
#include <bits/stdc++.h>
using namespace std;
// Function to find the previous
// fibonacci for the number N
int previousFibonacci(int n)
{
double a = n / ((1 + sqrt(5)) / 2.0);
return round(a);
}
// Function to find the next
// fibonacci number for the number N
int nextFibonacci(int n)
{
double a = n * (1 + sqrt(5)) / 2.0;
return round(a);
}
// Function to check that a Number
// is a perfect square or not
bool isPerfectSquare(int x)
{
int s = sqrt(x);
return (s * s == x);
}
// Function to check that a number
// is fibonacci number or not
bool isFibonacci(int n)
{
// N is Fibonacci if one of
// (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 count the fibonacci
// pairs in the array
int countFibonacciPairs(int arr[], int n)
{
int res = 0;
// Loop to iterate over the array
// to choose all pairs of the array
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
// Condition to check if both
// the number of pair is a
// fibonacci number
if (isFibonacci(arr[i])
&& isFibonacci(arr[j])) {
int prevFib = previousFibonacci(arr[i]);
int nextFib = nextFibonacci(arr[i]);
// Condition to check if both
// the number form consecutive
// fibonacci numbers
if (prevFib == arr[j]
|| nextFib == arr[j]) {
res++;
}
}
return res;
}
// Driver Code
int main()
{
int a[] = { 3, 5, 8, 11 };
int n = sizeof(a) / sizeof(a[0]);
cout << countFibonacciPairs(a, n);
return 0;
}
Java
// Java implementation to count the
// consecutive fibonacci pairs in the array
import java.util.*;
import java.lang.*;
class GFG
{
// Function to find the previous
// fibonacci for the number N
static int previousFibonacci(int n)
{
double a = n / ((1 + (int)Math.sqrt(5)) / 2.0);
return (int)Math.round(a);
}
// Function to find the next
// fibonacci number for the number N
static int nextFibonacci(int n)
{
double a = n * (1 + (int)Math.sqrt(5)) / 2.0;
return (int)Math.round(a);
}
// Function to check that a Number
// is a perfect square or not
static boolean isPerfectSquare(int x)
{
int s = (int)Math.sqrt(x);
return (s * s == x);
}
// Function to check that a number
// is fibonacci number or not
static boolean isFibonacci(int n)
{
// N is Fibonacci if one of
// (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 count the fibonacci
// pairs in the array
static int countFibonacciPairs(int arr[], int n)
{
int res = 0;
// Loop to iterate over the array
// to choose all pairs of the array
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
// Condition to check if both
// the number of pair is a
// fibonacci number
if (isFibonacci(arr[i])
&& isFibonacci(arr[j])) {
int prevFib = previousFibonacci(arr[i]);
int nextFib = nextFibonacci(arr[i]);
// Condition to check if both
// the number form consecutive
// fibonacci numbers
if (prevFib == arr[j]
|| nextFib == arr[j]) {
res++;
}
}
return res;
}
// Driver Code
public static void main(String []args)
{
int []a = { 3, 5, 8, 11 };
int n = a.length;
System.out.print(countFibonacciPairs(a, n));
}
}
// This code is contributed by chitranayal
Python3
# Python3 implementation to count the # consecutive fibonacci pairs in the array from math import sqrt # Function to find the previous # fibonacci for the number N def previousFibonacci(n): a = n / ((1 + sqrt(5)) / 2.0) return round(a) # Function to find the next # fibonacci number for the number N def nextFibonacci(n): a = n * (1 + sqrt(5)) / 2.0 return round(a) # Function to check that a Number # is a perfect square or not def isPerfectSquare(x): s = sqrt(x) return (s * s == x) # Function to check that a number # is fibonacci number or not def isFibonacci(n): # N is Fibonacci if one of # (5*n*n + 4) or (5*n*n - 4) # is a perfect square return (isPerfectSquare(5 * n * n + 4) or isPerfectSquare(5 * n * n - 4)) # Function to count the fibonacci # pairs in the array def countFibonacciPairs(arr, n): res = 0 # Loop to iterate over the array # to choose all pairs of the array for i in range(n): for j in range(i+1,n): # Condition to check if both # the number of pair is a # fibonacci number if (isFibonacci(arr[i]) and isFibonacci(arr[j])): prevFib = previousFibonacci(arr[i]) nextFib = nextFibonacci(arr[i]) # Condition to check if both # the number form consecutive # fibonacci numbers if (prevFib == arr[j] or nextFib == arr[j]): res += 1 return res # Driver Code a = [3, 5, 8, 11] n = len(a) print(countFibonacciPairs(a, n)) # This code is contributed by mohit kumar 29
C#
// C# implementation to count the
// consecutive fibonacci pairs in the array
using System;
class GFG
{
// Function to find the previous
// fibonacci for the number N
static int previousFibonacci(int n)
{
double a = n / ((1 + (int)Math.Sqrt(5)) / 2.0);
return (int)Math.Round(a);
}
// Function to find the next
// fibonacci number for the number N
static int nextFibonacci(int n)
{
double a = n * (1 + Math.Sqrt(5)) / 2.0;
return (int)Math.Round(a);
}
// Function to check that a Number
// is a perfect square or not
static bool isPerfectSquare(int x)
{
int s = (int)Math.Sqrt(x);
return (s * s == x);
}
// Function to check that a number
// is fibonacci number or not
static bool isFibonacci(int n)
{
// N is Fibonacci if one of
// (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 count the fibonacci
// pairs in the array
static int countFibonacciPairs(int []arr, int n)
{
int res = 0;
// Loop to iterate over the array
// to choose all pairs of the array
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
// Condition to check if both
// the number of pair is a
// fibonacci number
if (isFibonacci(arr[i])
&& isFibonacci(arr[j])) {
int prevFib = previousFibonacci(arr[i]);
int nextFib = nextFibonacci(arr[i]);
// Condition to check if both
// the number form consecutive
// fibonacci numbers
if (prevFib == arr[j]
|| nextFib == arr[j]) {
res++;
}
}
return res;
}
// Driver Code
public static void Main(String []args)
{
int []a = { 3, 5, 8, 11 };
int n = a.Length;
Console.Write(countFibonacciPairs(a, n));
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript implementation to count the
// consecutive fibonacci pairs in the array
// Function to find the previous
// fibonacci for the number N
function previousFibonacci(n)
{
var a = n / ((1 + Math.sqrt(5)) / 2.0);
return Math.round(a);
}
// Function to find the next
// fibonacci number for the number N
function nextFibonacci(n)
{
var a = n * (1 + Math.sqrt(5)) / 2.0;
return Math.round(a);
}
// Function to check that a Number
// is a perfect square or not
function isPerfectSquare(x)
{
var s = Math.sqrt(x);
return (s * s == x);
}
// Function to check that a number
// is fibonacci number or not
function isFibonacci(n)
{
// N is Fibonacci if one of
// (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 count the fibonacci
// pairs in the array
function countFibonacciPairs(arr, n)
{
var res = 0;
// Loop to iterate over the array
// to choose all pairs of the array
for (var i = 0; i < n; i++)
for (var j = i + 1; j < n; j++)
// Condition to check if both
// the number of pair is a
// fibonacci number
if (isFibonacci(arr[i])
&& isFibonacci(arr[j])) {
var prevFib = previousFibonacci(arr[i]);
var nextFib = nextFibonacci(arr[i]);
// Condition to check if both
// the number form consecutive
// fibonacci numbers
if (prevFib == arr[j]
|| nextFib == arr[j]) {
res++;
}
}
return res;
}
// Driver Code
var a = [ 3, 5, 8, 11 ];
var n = a.length;
document.write(countFibonacciPairs(a, n));
</script>
Producción:
2
Análisis de rendimiento:
- Complejidad del tiempo: como en el enfoque anterior, hay dos bucles anidados que requieren un tiempo O(N 2 ), por lo que la complejidad del tiempo será O(N 2 ) .
- Complejidad espacial: como en el enfoque anterior, no se utiliza espacio adicional, por lo que la complejidad espacial será O(1) .