GCD of elements occurring Fibonacci number of times in an Array | 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
function createHash ( hash , maxElement ) { let prev = 0 , curr = 1 ; hash . add ( prev ) ; hash . add ( curr ) ; while ( curr <= maxElement ) { let temp = curr + prev ; hash . add ( temp ) ; prev = curr ; curr = temp ; } } function gcdFibonacciFreq ( arr , n ) { let hash = new Set ( ) ; createHash ( hash , arr . sort ( ( a , b ) => b - a ) [ 0 ] ) ; let i , j ; let m = new Map ( ) ; for ( i = 0 ; i < n ; i ++ ) { if ( m . has ( arr [ i ] ) ) { m . set ( arr [ i ] , m . get ( arr [ i ] ) + 1 ) } else { m . set ( arr [ i ] , 1 ) } } let gcd = 0 ; for ( let it of m ) { if ( hash . has ( it [ 1 ] ) ) { gcd = __gcd ( gcd , it [ 0 ] ) ; } } return gcd ; } function __gcd ( a , b ) { return ( b == 0 ? a : __gcd ( b , a % b ) ) ; } let arr = [ 5 , 3 , 6 , 5 , 6 , 6 , 5 , 5 ] ; let n = arr . length ; document . write ( gcdFibonacciFreq ( arr , n ) ) ;