Dado un arreglo arr[] de elementos enteros, la tarea es encontrar la longitud del subarreglo más grande de arr[] tal que todos los elementos del subarreglo sean números de Fibonacci .
Ejemplos:
Entrada: arr[] = {11, 8, 21, 5, 3, 28, 4}
Salida: 4
Explicación:
la subarray de longitud máxima con todos los elementos como número de Fibonacci es {8, 21, 5, 3}.Entrada: arr[] = {25, 100, 36}
Salida: 0
Enfoque: este problema se puede resolver recorriendo la array arr[] . Siga los pasos a continuación para resolver este problema.
- Inicialice las variables, digamos, max_length y current_length como 0 para almacenar la longitud máxima de la subarray y la longitud actual de la subarray de modo que cada elemento de la subarray sea el número de Fibonacci .
- Iterar en el rango [0, N-1] usando la variable i :
- Si el número actual es un número de Fibonacci , aumente la longitud_actual en 1 ; de lo contrario, establezca la longitud_actual en 0.
- Ahora, asigne max_length como máximo de current_length y max_length.
- Después de completar los pasos anteriores, imprima max_length como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#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)
{
// Here n is Fibinac ci 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 length of the
// largest sub-array of an array every
// element of whose is a Fibonacci number
int contiguousFibonacciNumber(int arr[], int n)
{
int current_length = 0;
int max_length = 0;
// Traverse the array arr[]
for (int i = 0; i < n; i++) {
// Check if arr[i] is a Fibonacci number
if(isFibonacci(arr[i])) {
current_length++;
}
else{
current_length = 0;
}
// Stores the maximum length of the
// Fibonacci number subarray
max_length = max(max_length, current_length);
}
// Finally, return the maximum length
return max_length;
}
// Driver code
int main()
{
// Given Input
int arr[] = { 11, 8, 21, 5, 3, 28, 4};
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << contiguousFibonacciNumber(arr, n);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG
{
// A utility function that returns
// true if x is perfect square
public 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
public static boolean isFibonacci(int n)
{
// Here 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 length of the
// largest sub-array of an array every
// element of whose is a Fibonacci number
public static int contiguousFibonacciNumber(int arr[], int n)
{
int current_length = 0;
int max_length = 0;
// Traverse the array arr[]
for (int i = 0; i < n; i++) {
// Check if arr[i] is a Fibonacci number
if (isFibonacci(arr[i])) {
current_length++;
}
else {
current_length = 0;
}
// Stores the maximum length of the
// Fibonacci number subarray
max_length = Math.max(max_length, current_length);
}
// Finally, return the maximum length
return max_length;
}
// Driver code
public static void main (String[] args)
{
// Given Input
int arr[] = { 11, 8, 21, 5, 3, 28, 4 };
int n = arr.length;
// Function Call
System.out.println( contiguousFibonacciNumber(arr, n));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python3 program for the above approach import math # A utility function that returns # true if x is perfect square def isPerfectSquare(x): s = int(math.sqrt(x)) if s * s == x: return True else: return False # Returns true if n is a # Fibonacci Number, else false def isFibonacci(n): # Here 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 the length of the # largest sub-array of an array every # element of whose is a Fibonacci number def contiguousFibonacciNumber(arr, n): current_length = 0 max_length = 0 # Traverse the array arr for i in range(0, n): # Check if arr[i] is a Fibonacci number if isFibonacci(arr[i]): current_length += 1 else: current_length = 0 # stores the maximum length of the # Fibonacci number subarray max_length = max(max_length, current_length) # Finally, return the maximum length return max_length # Driver code if __name__ == '__main__': # Given Input arr = [ 11, 8, 21, 5, 3, 28, 4 ] n = len(arr) # Function Call print(contiguousFibonacciNumber(arr, n)) # This code is contributed by MuskanKalra1
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// A utility function that returns
// true if x is 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)
{
// Here 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 length of the
// largest sub-array of an array every
// element of whose is a Fibonacci number
static int contiguousFibonacciNumber(int []arr, int n)
{
int current_length = 0;
int max_length = 0;
// Traverse the array arr[]
for(int i = 0; i < n; i++)
{
// Check if arr[i] is a Fibonacci number
if (isFibonacci(arr[i]))
{
current_length++;
}
else
{
current_length = 0;
}
// Stores the maximum length of the
// Fibonacci number subarray
max_length = Math.Max(max_length,
current_length);
}
// Finally, return the maximum length
return max_length;
}
// Driver code
public static void Main()
{
// Given Input
int []arr = { 11, 8, 21, 5, 3, 28, 4 };
int n = arr.Length;
// Function Call
Console.Write(contiguousFibonacciNumber(arr, n));
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// JavaScript program for the above approach
// A utility function that returns
// true if x is perfect square
function isPerfectSquare(x) {
let s = parseInt(Math.sqrt(x));
return (s * s == x);
}
// Returns true if n is a
// Fibonacci Number, else false
function isFibonacci(n)
{
// Here 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 length of the
// largest sub-array of an array every
// element of whose is a Fibonacci number
function contiguousFibonacciNumber(arr, n) {
let current_length = 0;
let max_length = 0;
// Traverse the array arr[]
for (let i = 0; i < n; i++) {
// Check if arr[i] is a Fibonacci number
if (isFibonacci(arr[i])) {
current_length++;
}
else {
current_length = 0;
}
// Stores the maximum length of the
// Fibonacci number subarray
max_length = Math.max(max_length, current_length);
}
// Finally, return the maximum length
return max_length;
}
// Driver code
// Given Input
let arr = [11, 8, 21, 5, 3, 28, 4];
let n = arr.length;
// Function Call
document.write(contiguousFibonacciNumber(arr, n));
// This code is contributed by Potta Lokesh
</script>
Producción
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)