Encuentre el MCD de todos los números de array para los cuales su valor es igual a su frecuencia

Dada una array arr[] de números enteros N, la tarea es encontrar el GCD de todos los números para los que su valor es igual a su frecuencia en la array.

Ejemplos ;

Entrada : arr={2, 3, 4, 2, 3, 3} N=6    
Salida: 1
Explicación : Aquí 2 ocurre 2 veces y 3 ocurre 3 veces. 
Por lo tanto, MCD de 2, 3, es 1. Entonces nuestra salida es 1.
                      
Entrada : arr={2, 3, 4, 4, 3, 5, 4, 4, 2, 8} N=10      
Salida : 2
Explicación : Aquí 2 ocurre 2 veces, 4 ocurre 4 veces. 
Por lo tanto, GCD de 2, 4, es 2. Entonces nuestra salida es 2.
               

Enfoque : La idea para resolver el problema es la siguiente:

Encuentra los elementos cuyo valor es igual a su frecuencia . Luego calcula el MCD de esos números.

Siga los pasos que se mencionan a continuación para resolver el problema:

• Encuentre las frecuencias de todos los números de la array . 
• En la array, busque los números que tengan la misma frecuencia que su valor y guárdelos.
• Calcula el MCD de esos números.
• Devolver el GCD .

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find GCD
int findGcd(int arr[], int n)
{
    vector<int> v;
 
    // Declaration of map
    unordered_map<int, int> m1;
    for (int i = 0; i < n; i++) {
        m1[arr[i]]++;
    }
    unordered_map<int, int>::iterator it;
    for (it = m1.begin(); it != m1.end();
         ++it) {
        if (it->second == it->first)
 
            // Pushing superior numbers
            // into vector.
            v.push_back(it->first);
    }
    int hcf;
    if (v.size() == 0)
        return 0;
    else if (v.size() == 1)
        return v[0];
    else if (v.size() == 2) {
        hcf = __gcd(v[0], v[1]);
        return hcf;
    }
    else if (v.size() > 2) {
        hcf = __gcd(v[0], v[1]);
        for (int i = 2; i < v.size(); i++) {
            hcf = __gcd(v[i], hcf);
        }
        return hcf;
    }
    return 1;
}
 
// Driver Code
int main()
{
    int N = 10;
    int arr[N] = { 2, 3, 4, 4, 3,
                   5, 4, 4, 2, 8 };
 
    // Function call
    cout << findGcd(arr, N);
    return 0;
}

// Java code to implement the approach
import java.io.*;
import java.util.*;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
 
class GFG {
  public static int gcd(int a, int b)
  {
    if (b == 0)
      return a;
    return gcd(b, a % b);
  }
  // Function to find GCD
  public static int findGcd(int arr[], int n)
  {
    ArrayList<Integer> v = new ArrayList<Integer>();
 
    // Declaration of map
    HashMap<Integer, Integer> m1
      = new HashMap<Integer, Integer>();
    for (int i = 0; i < n; i++) {
      if (m1.get(arr[i]) != null)
        m1.put(arr[i], m1.get(arr[i]) + 1);
      else
        m1.put(arr[i], 1);
    }
    Iterator<Entry<Integer, Integer> > iter
      = m1.entrySet().iterator();
 
    // Iterating every set of entry in the HashMap
    while (iter.hasNext()) {
      Map.Entry<Integer, Integer> it
        = (Map.Entry<Integer, Integer>)iter.next();
 
      if (it.getValue() == it.getKey())
 
        // Pushing superior numbers
        // into vector.
        v.add(it.getKey());
    }
    int hcf = 0;
    if (v.size() == 0)
      return 0;
    else if (v.size() == 1)
      return v.get(0);
    else if (v.size() == 2) {
      hcf = gcd(v.get(0), v.get(1));
      return hcf;
    }
    else if (v.size() > 2) {
      hcf = gcd(v.get(0), v.get(1));
      for (int i = 2; i < v.size(); i++) {
        hcf = gcd(v.get(i), hcf);
      }
      return hcf;
    }
    return 1;
  }
  public static void main(String[] args)
  {
    int N = 10;
    int arr[] = { 2, 3, 4, 4, 3, 5, 4, 4, 2, 8 };
 
    // Function call
    System.out.print(findGcd(arr, N));
  }
}
 
// This code is contributed by Rohit Pradhan

# Python3 code to implement the approach
import math
 
# Function to find GCD
def findGcd(arr, n):
 
    v = []
     
    # Declaration of map/dictionary
    m1 = dict()
    for i in range(n):
        if arr[i] in m1:
            m1[arr[i]] += 1
        else:
            m1[arr[i]] = 1
 
    for it in m1:
 
        if m1[it] == it:
            v.append(it)
 
    if len(v) == 0:
        return 0
    elif len(v) == 1:
        return v[0]
    elif len(v) == 2:
        hcf = math.gcd(v[0], v[1])
        return hcf
    elif len(v) > 2:
        hcf = math.gcd(v[0], v[1])
        for i in range(2, len(v)):
            hcf = math.gcd(hcf, v[i])
        return hcf
    return 1
 
# driver code
N = 10
arr = [2, 3, 4, 4, 3, 5, 4, 4, 2, 8]
 
# function call
print(findGcd(arr, N))
 
# This code is contributed by phasing17.

// C# code to implement the approach
using System;
using System.Collections.Generic;
 
public class GFG
{
   
    // Function to calculate GCD
    public static int gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
 
    // Function to find GCD
    public static int findGcd(int[] arr, int n)
    {
        List<int> v = new List<int>();
 
        // Declaration of dictionary
        IDictionary<int, int> m1
            = new Dictionary<int, int>();
        // building the frequency dictionary
        for (int i = 0; i < n; i++) {
            if (m1.ContainsKey(arr[i]))
                m1[arr[i]] += 1;
            else
                m1[arr[i]] = 1;
        }
 
        // iterating over each entry in m1
        // to find which keys have equivalent values
        foreach(KeyValuePair<int, int> entry in m1)
        {
            if (entry.Value == entry.Key)
                v.Add(entry.Value);
        }
 
        // calculating gcd
        int hcf = 0;
        if (v.Count == 0)
            return 0;
        if (v.Count == 1)
            return v[0];
        if (v.Count == 2) {
            hcf = gcd(v[0], v[1]);
            return hcf;
        }
 
        if (v.Count > 2) {
            hcf = gcd(v[0], v[1]);
            for (int i = 2; i < v.Count; i++) {
                hcf = gcd(v[i], hcf);
            }
            return hcf;
        }
        return 1;
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        int N = 10;
        int[] arr = { 2, 3, 4, 4, 3, 5, 4, 4, 2, 8 };
 
        // Function call
        Console.WriteLine(findGcd(arr, N));
    }
}
 
// this code is contributed by phasing17

<script>
// JavaScript code to implement the approach
'use strict';
 
// Function for calculating gcd
function gcd(a, b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
 
 
// Function to find GCD
function findGcd(arr, n)
{
 
    var v = [];
     
    // Declaration of map
    var m1 = {};
    for (var i = 0; i < n; i++)
    {
        if (m1.hasOwnProperty(arr[i]))
            m1[arr[i]] += 1;
        else
            m1[arr[i]] = 1;
    }
     
    //iterating through all the keys of m1
    for (const it of Object.keys(m1))
        {
            if (m1[it] == it)
                v.push(it);
        }
 
    if (v.length == 0)
        return 0;
    else if (v.length == 1)
        return v[0];
    else if (v.length == 2)
        {
            var hcf = gcd(v[0], v[1]);
            return hcf;
        }
    else if (v.length > 2)
        {
            var hcf = math.gcd(v[0], v[1]);
            for (var i = 2; i < v.length; i++)
                hcf = math.gcd(hcf, v[i]);
            return hcf;
        }
    return 1;
}
// driver code
var N = 10;
var arr = [2, 3, 4, 4, 3, 5, 4, 4, 2, 8];
 
// function call
document.write(findGcd(arr, N));
 
// This code is contributed by phasing17.
</script>

2

Complejidad de tiempo: el tiempo requerido para encontrar gcd de todos los elementos en el vector será la complejidad de tiempo general. vector a la vez puede tener el número máximo de elementos únicos de la array.

asi que 

• tiempo necesario para encontrar mcd de dos elementos log (max (dos números))
• por lo que el tiempo necesario para encontrar el mcd de todos los elementos únicos será O(elementos únicos *log(max(dos números)))

Entonces, la complejidad del tiempo será O (total de elementos únicos * log (máximo (ambos números)))

de manera más amplia, podemos decir que la complejidad del tiempo debe ser O (número total de elementos únicos * Log (n)) o podemos decir O (n * log (n)).
Espacio Auxiliar: O(N)