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
using System ; using System . Linq ; using System . Collections . Generic ; class GFG { static void createHash ( HashSet < int > hash , int maxElement ) { int prev = 0 , curr = 1 ; hash . Add ( prev ) ; hash . Add ( curr ) ; while ( curr <= maxElement ) { int temp = curr + prev ; hash . Add ( temp ) ; prev = curr ; curr = temp ; } } static int gcdFibonacciFreq ( int [ ] arr , int n ) { HashSet < int > hash = new HashSet < int > ( ) ; createHash ( hash , hash . Count > 0 ? hash . Max ( ) : 0 ) ; int i ; Dictionary < int , int > m = new Dictionary < int , int > ( ) ; for ( i = 0 ; i < n ; i ++ ) { if ( m . ContainsKey ( arr [ i ] ) ) { m [ arr [ i ] ] = m [ arr [ i ] ] + 1 ; } else { m . Add ( arr [ i ] , 1 ) ; } } int gcd = 0 ; foreach ( KeyValuePair < int , int > it in m ) { if ( hash . Contains ( it . Value ) ) { gcd = __gcd ( gcd , it . Key ) ; } } return gcd ; } static int __gcd ( int a , int b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } public static void Main ( String [ ] args ) { int [ ] arr = { 5 , 3 , 6 , 5 , 6 , 6 , 5 , 5 } ; int n = arr . Length ; Console . Write ( gcdFibonacciFreq ( arr , n ) ) ; } }