Check if sum of Fibonacci elements in an Array is a Fibonacci number or not | C ++ program to check whether the sum of fibonacci elements of the array is a Fibonacci number or not ; Hash to store the Fibonacci numbers up to Max ; Function to create the hash table to check Fibonacci numbers ; Inserting the first two Fibonacci numbers into the hash ; Add the remaining Fibonacci numbers based on the previous two numbers ; Function to check if the sum of Fibonacci numbers is Fibonacci or not ; Find the sum of all Fibonacci numbers ; Iterating through the array ; If the sum is Fibonacci then return true ; Driver code ; array of elements ; Creating a set containing all fibonacci numbers
#include <bits/stdc++.h> NEW_LINE #define ll  long long int NEW_LINE #define MAX  100005 NEW_LINE using namespace std ; set < int > fibonacci ; void createHash ( ) { int prev = 0 , curr = 1 ; fibonacci . insert ( prev ) ; fibonacci . insert ( curr ) ; while ( curr <= MAX ) { int temp = curr + prev ; fibonacci . insert ( temp ) ; prev = curr ; curr = temp ; } } bool checkArray ( int arr [ ] , int n ) { ll sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) if ( fibonacci . find ( arr [ i ] ) != fibonacci . end ( ) ) sum += arr [ i ] ; if ( fibonacci . find ( sum ) != fibonacci . end ( ) ) return true ; return false ; } int main ( ) { int arr [ ] = { 1 , 2 , 4 , 8 , 2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; createHash ( ) ; if ( checkArray ( arr , n ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }