Longitud del subarreglo de Fibonacci más largo

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)

Publicación traducida automáticamente

Artículo escrito por spp____ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *