Count of total subarrays whose sum is a Fibonacci Numbers | C ++ program for the above approach ; Function to check whether a number is perfect square or not ; Function to check whether a number is fibonacci number or not ; If 5 * n * n + 4 or 5 * n * n - 5 is a perfect square , then the number is Fibonacci ; Function to count the subarray with sum fibonacci number ; Traverse the array arr [ ] to find the sum of each subarray ; To store the sum ; Check whether sum of subarray between [ i , j ] is fibonacci or not ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPerfectSquare ( int x ) { int s = sqrt ( x ) ; return ( s * s == x ) ; } bool isFibonacci ( int n ) { return isPerfectSquare ( 5 * n * n + 4 ) || isPerfectSquare ( 5 * n * n - 4 ) ; } void fibonacciSubarrays ( int arr [ ] , int n ) { int count = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int sum = 0 ; for ( int j = i ; j < n ; ++ j ) { sum += arr [ j ] ; if ( isFibonacci ( sum ) ) { ++ count ; } } } cout << count ; } int main ( ) { int arr [ ] = { 6 , 7 , 8 , 9 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; fibonacciSubarrays ( arr , n ) ; return 0 ; }