Dada una array arr[] de N enteros, la tarea es contar el número total de subarreglos cuya suma es un número de Fibonacci .
Ejemplos:
Entrada: arr[] = {6, 7, 8, 9}
Salida: 3
Explicación:
El subarreglo cuya suma son los números de Fibonacci son:
1. {6, 7}, suma = 13 (5 + 8)
2. {6, 7, 8}, sum = 21 (8 + 13)
3. {8}, sum = 8 (3 + 5)
Entrada: arr[] = {1, 1, 1, 1}
Salida: 4
Explicación:
El subarreglo cuyo suma es los números de fibonacci son:
1. {4, 2, 2}, suma = 8 (3 + 5)
2. {2}, suma = 2 (1 + 1)
3. {2}, suma = 2 (1 + 1)
4. {2}, suma = 2 (1 + 1)
Enfoque: La idea es generar todos los subarreglos posibles y encontrar la suma de cada subarreglo. Ahora, para cada suma, verifique si es Fibonacci o no utilizando el enfoque discutido en este artículo. En caso afirmativo, cuente todas esas sumas e imprima el recuento total.
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;
// Function to check whether a number
// is perfect square or not
bool isPerfectSquare(int x)
{
int s = sqrt(x);
return (s * s == x);
}
// Function to check whether a number
// is fibonacci number or not
bool isFibonacci(int n)
{
// If 5*n*n + 4 or 5*n*n - 5 is a
// perfect square, then the number
// is Fibonacci
return isPerfectSquare(5 * n * n + 4)
|| isPerfectSquare(5 * n * n - 4);
}
// Function to count the subarray with
// sum fibonacci number
void fibonacciSubarrays(int arr[], int n)
{
int count = 0;
// Traverse the array arr[] to find
// the sum of each subarray
for (int i = 0; i < n; ++i) {
// To store the sum
int sum = 0;
for (int j = i; j < n; ++j) {
sum += arr[j];
// Check whether sum of subarray
// between [i, j] is fibonacci
// or not
if (isFibonacci(sum)) {
++count;
}
}
}
cout << count;
}
// Driver Code
int main()
{
int arr[] = { 6, 7, 8, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
fibonacciSubarrays(arr, n);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to check whether a number
// is perfect square or not
static boolean isPerfectSquare(int x)
{
int s = (int) Math.sqrt(x);
return (s * s == x);
}
// Function to check whether a number
// is fibonacci number or not
static boolean isFibonacci(int n)
{
// If 5*n*n + 4 or 5*n*n - 5 is a
// perfect square, then the number
// is Fibonacci
return isPerfectSquare(5 * n * n + 4)
|| isPerfectSquare(5 * n * n - 4);
}
// Function to count the subarray
// with sum fibonacci number
static void fibonacciSubarrays(int arr[], int n)
{
int count = 0;
// Traverse the array arr[] to find
// the sum of each subarray
for (int i = 0; i < n; ++i) {
// To store the sum
int sum = 0;
for (int j = i; j < n; ++j) {
sum += arr[j];
// Check whether sum of subarray
// between [i, j] is fibonacci
// or not
if (isFibonacci(sum)) {
++count;
}
}
}
System.out.print(count);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 6, 7, 8, 9 };
int n = arr.length;
// Function Call
fibonacciSubarrays(arr, n);
}
}
// This code contributed by PrinciRaj1992
Python3
# Python3 program for the above approach import math # Function to check whether a number # is perfect square or not def isPerfectSquare(x): s = int(math.sqrt(x)) if s * s == x: return True return False # Function to check whether a number # is fibonacci number or not def isFibonacci(n): # If 5*n*n + 4 or 5*n*n - 5 is a # perfect square, then the number # is Fibonacci return (isPerfectSquare(5 * n * n + 4) or isPerfectSquare(5 * n * n - 4)) # Function to count the subarray with # sum fibonacci number def fibonacciSubarrays(arr, n): count = 0 # Traverse the array arr[] to find # the sum of each subarray for i in range(n): # To store the sum sum = 0 for j in range(i, n): sum += arr[j] # Check whether sum of subarray # between [i, j] is fibonacci # or not if (isFibonacci(sum)): count += 1 print(count) # Driver Code arr = [ 6, 7, 8, 9 ] n = len(arr) # Function Call fibonacciSubarrays(arr, n) # This code is contributed by SHUBHAMSINGH10
C#
// C# program for the above approach
using System;
class GFG{
// Function to check whether a number
// is perfect square or not
static bool isPerfectSquare(int x)
{
int s = (int) Math.Sqrt(x);
return (s * s == x);
}
// Function to check whether a number
// is fibonacci number or not
static bool isFibonacci(int n)
{
// If 5*n*n + 4 or 5*n*n - 5 is a
// perfect square, then the number
// is Fibonacci
return isPerfectSquare(5 * n * n + 4) ||
isPerfectSquare(5 * n * n - 4);
}
// Function to count the subarray
// with sum fibonacci number
static void fibonacciSubarrays(int []arr, int n)
{
int count = 0;
// Traverse the array []arr to find
// the sum of each subarray
for(int i = 0; i < n; ++i)
{
// To store the sum
int sum = 0;
for(int j = i; j < n; ++j)
{
sum += arr[j];
// Check whether sum of subarray
// between [i, j] is fibonacci
// or not
if (isFibonacci(sum))
{
++count;
}
}
}
Console.Write(count);
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 6, 7, 8, 9 };
int n = arr.Length;
// Function Call
fibonacciSubarrays(arr, n);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above approach
// Function to check whether a number
// is perfect square or not
function isPerfectSquare(x)
{
var s = parseInt(Math.sqrt(x));
return (s * s == x);
}
// Function to check whether a number
// is fibonacci number or not
function isFibonacci(n)
{
// If 5*n*n + 4 or 5*n*n - 5 is a
// perfect square, then the number
// is Fibonacci
return isPerfectSquare(5 * n * n + 4)
|| isPerfectSquare(5 * n * n - 4);
}
// Function to count the subarray with
// sum fibonacci number
function fibonacciSubarrays(arr, n)
{
var count = 0;
// Traverse the array arr[] to find
// the sum of each subarray
for (var i = 0; i < n; ++i) {
// To store the sum
var sum = 0;
for (var j = i; j < n; ++j) {
sum += arr[j];
// Check whether sum of subarray
// between [i, j] is fibonacci
// or not
if (isFibonacci(sum)) {
++count;
}
}
}
document.write( count);
}
// Driver Code
var arr = [ 6, 7, 8, 9 ];
var n = arr.length;
// Function Call
fibonacciSubarrays(arr, n);
</script>
Producción:
3
Complejidad temporal: O(N 2 ) , donde N es el número de elementos.
Espacio Auxiliar: O(1)