GCD de elementos que ocurren el número de veces de Fibonacci en una array

Dada una array arr[] que contiene N elementos, la tarea es encontrar el GCD de los elementos que tienen un recuento de frecuencia, que es un número de Fibonacci en la array.
Ejemplos: 
 

Entrada: arr[] = { 5, 3, 6, 5, 6, 6, 5, 5 } 
Salida: 3 
Explicación: los 
elementos 5, 3, 6 aparecen 4, 1, 3 veces respectivamente. 
Por lo tanto, 3 y 6 tienen frecuencias de Fibonacci. 
Entonces, mcd(3, 6) = 1
Entrada: arr[] = {4, 2, 3, 3, 3, 3} 
Salida: 2 
Explicación: 
Los elementos 4, 2, 3 aparecen 1, 1, 4 veces respectivamente. 
Por lo tanto, 4 y 2 tienen frecuencias de Fibonacci. 
Entonces mcd(4, 2) = 2 
 

Enfoque: La idea es usar hashing para precalcular y almacenar los Nodes de Fibonacci hasta el valor máximo para que la verificación sea fácil y eficiente (en tiempo O(1)).
Después de precalcular el hash : 
 

1. atravesar la array y almacenar las frecuencias de todos los elementos en un mapa .
2. Usando el mapa y el hash, calcule el gcd de los elementos que tienen la frecuencia de fibonacci usando el hash precalculado.

A continuación se muestra la implementación del enfoque anterior: 
 

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

// Java program to find the GCD of
// elements which occur Fibonacci
// number of times
import java.util.*;
 
class GFG{
  
// Function to create hash table
// to check Fibonacci numbers
static void createHash(HashSet<Integer> hash,
                int maxElement)
{
    // Inserting the first two
    // numbers into the hash
    int prev = 0, curr = 1;
    hash.add(prev);
    hash.add(curr);
  
    // Adding the remaining Fibonacci
    // numbers using the previously
    // added elements
    while (curr <= maxElement) {
        int temp = curr + prev;
        hash.add(temp);
        prev = curr;
        curr = temp;
    }
}
  
// Function to return the GCD of elements
// in an array having fibonacci frequency
static int gcdFibonacciFreq(int arr[], int n)
{
    HashSet<Integer> hash = new HashSet<Integer>();
  
    // Creating the hash
    createHash(hash,Arrays.stream(arr).max().getAsInt());
  
    int i;
  
    // Map is used to store the
    // frequencies of the elements
    HashMap<Integer,Integer> m = new HashMap<Integer,Integer>();
  
    // Iterating through the array
    for (i = 0; i < n; i++) {
        if(m.containsKey(arr[i])){
            m.put(arr[i], m.get(arr[i])+1);
        }
        else{
            m.put(arr[i], 1);
        }
    }
  
    int gcd = 0;
  
    // Traverse the map using iterators
    for (Map.Entry<Integer, Integer> it : m.entrySet()) {
  
        // Calculate the gcd of elements
        // having fibonacci frequencies
        if (hash.contains(it.getValue())) {
            gcd = __gcd(gcd,
                        it.getKey());
        }
    }
  
    return gcd;
}
static int __gcd(int a, int b) 
{ 
    return b == 0? a:__gcd(b, a % b);    
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 5, 3, 6, 5,
                  6, 6, 5, 5 };
    int n = arr.length;
  
    System.out.print(gcdFibonacciFreq(arr, n));
}
}
 
// This code is contributed by Princi Singh

# Python 3 program to find the GCD of
# elements which occur Fibonacci
# number of times
from collections import defaultdict
import math
  
# Function to create hash table
# to check Fibonacci numbers
def createHash(hash1,maxElement):
 
    # Inserting the first two
    # numbers into the hash
    prev , curr = 0, 1
    hash1.add(prev)
    hash1.add(curr)
  
    # Adding the remaining Fibonacci
    # numbers using the previously
    # added elements
    while (curr <= maxElement):
        temp = curr + prev
        if temp <= maxElement:
            hash1.add(temp)
        prev = curr
        curr = temp
  
# Function to return the GCD of elements
# in an array having fibonacci frequency
def gcdFibonacciFreq(arr, n):
 
    hash1 = set()
  
    # Creating the hash
    createHash(hash1,max(arr))
  
    # Map is used to store the
    # frequencies of the elements
    m = defaultdict(int)
  
    # Iterating through the array
    for i in range(n):
        m[arr[i]] += 1
  
    gcd = 0
  
    # Traverse the map using iterators
    for it in m.keys():
  
        # Calculate the gcd of elements
        # having fibonacci frequencies
        if (m[it] in hash1):
            gcd = math.gcd(gcd,it)
    return gcd
  
# Driver code
if __name__ == "__main__":
     
    arr = [ 5, 3, 6, 5,
                  6, 6, 5, 5 ]
    n = len(arr)
  
    print(gcdFibonacciFreq(arr, n))
  
 # This code is contributed by chitranayal

// C# program to find the GCD of
// elements which occur Fibonacci
// number of times
using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG{
   
// Function to create hash table
// to check Fibonacci numbers
static void createHash(HashSet<int> hash,
                int maxElement)
{
    // Inserting the first two
    // numbers into the hash
    int prev = 0, curr = 1;
    hash.Add(prev);
    hash.Add(curr);
   
    // Adding the remaining Fibonacci
    // numbers using the previously
    // added elements
    while (curr <= maxElement) {
        int temp = curr + prev;
        hash.Add(temp);
        prev = curr;
        curr = temp;
    }
}
   
// Function to return the GCD of elements
// in an array having fibonacci frequency
static int gcdFibonacciFreq(int []arr, int n)
{
    HashSet<int> hash = new HashSet<int>();
   
    // Creating the hash
    createHash(hash, hash.Count > 0 ? hash.Max():0);
   
    int i;
   
    // Map is used to store the
    // frequencies of the elements
    Dictionary<int,int> m = new Dictionary<int,int>();
   
    // Iterating through the array
    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;
   
    // Traverse the map using iterators
    foreach(KeyValuePair<int, int> it in m) {
   
        // Calculate the gcd of elements
        // having fibonacci frequencies
        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);    
}
  
// Driver code
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));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript program to find the GCD of
// elements which occur Fibonacci
// number of times
 
 
// Function to create hash table
// to check Fibonacci numbers
function createHash(hash, maxElement)
{
    // Inserting the first two
    // numbers into the hash
    let prev = 0, curr = 1;
    hash.add(prev);
    hash.add(curr);
 
    // Adding the remaining Fibonacci
    // numbers using the previously
    // added elements
    while (curr <= maxElement) {
        let temp = curr + prev;
        hash.add(temp);
        prev = curr;
        curr = temp;
    }
}
 
// Function to return the GCD of elements
// in an array having fibonacci frequency
function gcdFibonacciFreq(arr, n)
{
    let hash = new Set();
 
    // Creating the hash
    createHash(hash, arr.sort((a, b) => b - a)[0]);
 
    let i, j;
 
    // Map is used to store the
    // frequencies of the elements
    let m = new Map();
 
    // Iterating through the array
    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;
 
    // Traverse the map using iterators
    for (let it of m) {
 
        // Calculate the gcd of elements
        // having fibonacci frequencies
        if (hash.has(it[1])) {
            gcd = __gcd(gcd, it[0]);
        }
    }
 
    return gcd;
}
 
function __gcd(a, b) 
{ 
    return (b == 0? a:__gcd(b, a % b));    
}
 
// Driver code
 
 
let arr = [ 5, 3, 6, 5,
            6, 6, 5, 5 ];
let n = arr.length;
 
document.write(gcdFibonacciFreq(arr, n));
 
 
// This code is contributed by gfgking
 
</script>

3

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(N)