GCD of elements occurring Fibonacci number of times in an Array | Python 3 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
from collections import defaultdict NEW_LINE import math NEW_LINE def createHash ( hash1 , maxElement ) : NEW_LINE INDENT prev , curr = 0 , 1 NEW_LINE hash1 . add ( prev ) NEW_LINE hash1 . add ( curr ) NEW_LINE while ( curr <= maxElement ) : NEW_LINE INDENT temp = curr + prev NEW_LINE if temp <= maxElement : NEW_LINE INDENT hash1 . add ( temp ) NEW_LINE DEDENT prev = curr NEW_LINE curr = temp NEW_LINE DEDENT DEDENT def gcdFibonacciFreq ( arr , n ) : NEW_LINE INDENT hash1 = set ( ) NEW_LINE createHash ( hash1 , max ( arr ) ) NEW_LINE m = defaultdict ( int ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT m [ arr [ i ] ] += 1 NEW_LINE DEDENT gcd = 0 NEW_LINE for it in m . keys ( ) : NEW_LINE INDENT if ( m [ it ] in hash1 ) : NEW_LINE INDENT gcd = math . gcd ( gcd , it ) NEW_LINE DEDENT DEDENT return gcd NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 5 , 3 , 6 , 5 , 6 , 6 , 5 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE print ( gcdFibonacciFreq ( arr , n ) ) NEW_LINE DEDENT