GCD of elements occurring Fibonacci number of times in an Array | C ++ program to find the GCD of elements which occur Fibonacci number of times ; Function to create hash table to check Fibonacci numbers ; Inserting the first two numbers into the hash ; Adding the remaining Fibonacci numbers using the previously added elements ; Function to return the GCD of elements in an array having fibonacci frequency ; Creating the hash ; Map is used to store the frequencies of the elements ; Iterating through the array ; Traverse the map using iterators ; Calculate the gcd of elements having fibonacci frequencies ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void createHash ( set < int > & hash , int maxElement ) { int prev = 0 , curr = 1 ; hash . insert ( prev ) ; hash . insert ( curr ) ; while ( curr <= maxElement ) { int temp = curr + prev ; hash . insert ( temp ) ; prev = curr ; curr = temp ; } } int gcdFibonacciFreq ( int arr [ ] , int n ) { set < int > hash ; createHash ( hash , * max_element ( arr , arr + n ) ) ; int i , j ; unordered_map < int , int > m ; for ( i = 0 ; i < n ; i ++ ) m [ arr [ i ] ] ++ ; int gcd = 0 ; for ( auto it = m . begin ( ) ; it != m . end ( ) ; it ++ ) { if ( hash . find ( it -> second ) != hash . end ( ) ) { gcd = __gcd ( gcd , it -> first ) ; } } return gcd ; } int main ( ) { int arr [ ] = { 5 , 3 , 6 , 5 , 6 , 6 , 5 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << gcdFibonacciFreq ( arr , n ) ; return 0 ; }