Given an array arr[] of N integers, the task is to count total number of subarrays whose sum is a Fibonacci Number.
Examples:
Input: arr[] = {6, 7, 8, 9}
Output: 3
Explanation:
The subarray whose sum is fibonacci numbers are:
1. {6, 7}, sum = 13 (5 + 8)
2. {6, 7, 8}, sum = 21 (8 + 13)
3. {8}, sum = 8 (3 + 5)
Input: arr[] = {1, 1, 1, 1}
Output: 4
Explanation:
The subarray whose sum is fibonacci numbers are:
1. {4, 2, 2}, sum = 8 (3 + 5)
2. {2}, sum = 2 (1 + 1)
3. {2}, sum = 2 (1 + 1)
4. {2}, sum = 2 (1 + 1)
Approach: The idea is generate all possible subarray and find the sum of each subarray. Now for each sum check whether it is fibonacci or not by using the approach discussed in this article. If Yes then, count all those sum and print the total count.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check whether a number// is perfect square or notbool isPerfectSquare(int x){ int s = sqrt(x); return (s * s == x);}// Function to check whether a number// is fibonacci number or notbool 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 numbervoid 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 Codeint 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 approachclass GFG{// Function to check whether a number// is perfect square or notstatic boolean isPerfectSquare(int x){ int s = (int) Math.sqrt(x); return (s * s == x);}// Function to check whether a number// is fibonacci number or notstatic 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 numberstatic 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 Codepublic 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 approachimport math# Function to check whether a number# is perfect square or notdef 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 notdef 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 numberdef 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 Codearr = [ 6, 7, 8, 9 ]n = len(arr)# Function CallfibonacciSubarrays(arr, n)# This code is contributed by SHUBHAMSINGH10 |
C#
// C# program for the above approachusing System;class GFG{// Function to check whether a number// is perfect square or notstatic bool isPerfectSquare(int x){ int s = (int) Math.Sqrt(x); return (s * s == x);}// Function to check whether a number// is fibonacci number or notstatic 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 numberstatic 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 Codepublic 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 notfunction isPerfectSquare(x){ var s = parseInt(Math.sqrt(x)); return (s * s == x);}// Function to check whether a number// is fibonacci number or notfunction 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 numberfunction 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 Codevar arr = [ 6, 7, 8, 9 ];var n = arr.length;// Function CallfibonacciSubarrays(arr, n);</script> |
Output:
3
Time Complexity: O(N2), where N is the number of elements.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
