Nos dan una array de enteros positivos. Encuentre el par en la array con MCD máximo.
Ejemplos:
Input : arr[] : { 1 2 3 4 5 }
Output : 2
Explanation : Pair {2, 4} has GCD 2 which is highest. Other pairs have a GCD of 1.
Input : arr[] : { 2 3 4 8 8 11 12 }
Output : 8
Explanation : Pair {8, 8} has GCD 8 which is highest.
Método 1 (Fuerza bruta) : el método más simple para resolver este problema es usar dos bucles para generar todos los pares posibles de elementos de la array y calcular y comparar el GCD al mismo tiempo. Podemos usar el algoritmo euclidiano extendido para calcular eficientemente el GCD de dos números.
Complejidad de tiempo : O(N^2 * log(max(a, b)))
Aquí, log(max(a, b)) es la complejidad de tiempo para calcular GCD de a y b.
Método 2: (Eficiente)En este método, mantenemos una array de conteo para almacenar el conteo de divisores de cada elemento. Recorreremos la array dada y para cada elemento, calcularemos sus divisores e incrementaremos en el índice de la array de conteo. El proceso de cálculo de divisores tomará un tiempo O(sqrt(arr[i])), donde arr[i] es un elemento en la array dada en el índice i. Después de todo el recorrido, podemos simplemente recorrer la array de conteo desde el último índice hasta el índice 1. Si encontramos un índice con un valor mayor que 1, esto significa que es un divisor de 2 elementos y también el GCD máximo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Code to find pair with
// maximum GCD in an array
#include <bits/stdc++.h>
using namespace std;
// function to find GCD of pair with
// max GCD in the array
int findMaxGCD(int arr[], int n)
{
// Computing highest element
int high = 0;
for (int i = 0; i < n; i++)
high = max(high, arr[i]);
// Array to store the count of divisors
// i.e. Potential GCDs
int divisors[high + 1] = { 0 };
// Iterating over every element
for (int i = 0; i < n; i++)
{
// Calculating all the divisors
for (int j = 1; j <= sqrt(arr[i]); j++)
{
// Divisor found
if (arr[i] % j == 0)
{
// Incrementing count for divisor
divisors[j]++;
// Element/divisor is also a divisor
// Checking if both divisors are
// not same
if (j != arr[i] / j)
divisors[arr[i] / j]++;
}
}
}
// Checking the highest potential GCD
for (int i = high; i >= 1; i--)
// If this divisor can divide at least 2
// numbers, it is a GCD of at least 1 pair
if (divisors[i] > 1)
return i;
}
// Driver code
int main()
{
// Array in which pair with max GCD
// is to be found
int arr[] = { 1, 2, 4, 8, 8, 12 };
// Size of array
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMaxGCD(arr,n);
return 0;
}
Java
// JAVA Code for Find pair with maximum GCD in an array
class GFG {
// function to find GCD of pair with
// max GCD in the array
public static int findMaxGCD(int arr[], int n)
{
// Computing highest element
int high = 0;
for (int i = 0; i < n; i++)
high = Math.max(high, arr[i]);
// Array to store the count of divisors
// i.e. Potential GCDs
int divisors[] =new int[high + 1];
// Iterating over every element
for (int i = 0; i < n; i++)
{
// Calculating all the divisors
for (int j = 1; j <= Math.sqrt(arr[i]); j++)
{
// Divisor found
if (arr[i] % j == 0)
{
// Incrementing count for divisor
divisors[j]++;
// Element/divisor is also a divisor
// Checking if both divisors are
// not same
if (j != arr[i] / j)
divisors[arr[i] / j]++;
}
}
}
// Checking the highest potential GCD
for (int i = high; i >= 1; i--)
// If this divisor can divide at least 2
// numbers, it is a GCD of at least 1 pair
if (divisors[i] > 1)
return i;
return 1;
}
/* Driver program to test above function */
public static void main(String[] args)
{
// Array in which pair with max GCD
// is to be found
int arr[] = { 1, 2, 4, 8, 8, 12 };
// Size of array
int n = arr.length;
System.out.println(findMaxGCD(arr,n));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python
# Python program to Find pair with # maximum GCD in an array import math # function to find GCD of pair with # max GCD in the array def findMaxGCD(arr, n) : # Computing highest element high = 0 i = 0 while i < n : high = max(high, arr[i]) i = i + 1 # Array to store the count of divisors # i.e. Potential GCDs divisors = [0] * (high + 1) # Iterating over every element i = 0 while i < n : # Calculating all the divisors j = 1 while j <= math.sqrt(arr[i]) : # Divisor found if (arr[i] % j == 0) : # Incrementing count for divisor divisors[j]= divisors[j]+1 # Element/divisor is also a divisor # Checking if both divisors are # not same if (j != arr[i] / j) : divisors[arr[i] / j] = divisors[arr[i] / j] + 1 j = j + 1 i = i + 1 # Checking the highest potential GCD i = high while i >= 1 : # If this divisor can divide at least 2 # numbers, it is a GCD of at least 1 pair if (divisors[i] > 1) : return i i = i - 1 return 1 # Driver code # Array in which pair with max GCD # is to be found arr = [ 1, 2, 4, 8, 8, 12 ] # Size of array n = len(arr) print findMaxGCD(arr,n) # This code is contributed by Nikita Tiwari.
C#
// C# Code for Find pair with
// maximum GCD in an array
using System;
class GFG {
// Function to find GCD of pair
// with max GCD in the array
public static int findMaxGCD(int []arr,
int n)
{
// Computing highest element
int high = 0;
for (int i = 0; i < n; i++)
high = Math.Max(high, arr[i]);
// Array to store the count of
// divisors i.e. Potential GCDs
int []divisors =new int[high + 1];
// Iterating over every element
for (int i = 0; i < n; i++)
{
// Calculating all the divisors
for (int j = 1; j <=
Math.Sqrt(arr[i]); j++)
{
// Divisor found
if (arr[i] % j == 0)
{
// Incrementing count
// for divisor
divisors[j]++;
// Element / divisor is also
// a divisor Checking if both
// divisors are not same
if (j != arr[i] / j)
divisors[arr[i] / j]++;
}
}
}
// Checking the highest potential GCD
for (int i = high; i >= 1; i--)
// If this divisor can divide at
// least 2 numbers, it is a
// GCD of at least 1 pair
if (divisors[i] > 1)
return i;
return 1;
}
// Driver Code
public static void Main(String []args)
{
// Array in which pair with
// max GCD is to be found
int []arr = {1, 2, 4, 8, 8, 12};
// Size of array
int n = arr.Length;
Console.WriteLine(findMaxGCD(arr,n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP Code for Find pair with
// maximum GCD in an array
// Function to find GCD
// of pair with max GCD
// in the array
function findMaxGCD($arr, $n)
{
// Computing highest element
$high = 0;
for ($i = 0; $i < $n; $i++)
$high = max($high, $arr[$i]);
// Array to store the
// count of divisors
// i.e. Potential GCDs
$divisors = array_fill(0, $high + 1, 0);
// Iterating over every element
for ($i = 0; $i < $n; $i++)
{
// Calculating all
// the divisors
for ($j = 1;
$j <= (int)(sqrt($arr[$i])); $j++)
{
// Divisor found
if ($arr[$i] % $j == 0)
{
// Incrementing count
// for divisor
$divisors[$j]++;
// Element/divisor is also
// a divisor Checking if
// both divisors are not same
if ($j != (int)($arr[$i] / $j))
$divisors[(int)($arr[$i] / $j)]++;
}
}
}
// Checking the highest
// potential GCD
for ($i = $high; $i >= 1; $i--)
// If this divisor can divide
// at least 2 numbers, it is
// a GCD of at least 1 pair
if ($divisors[$i] > 1)
return $i;
}
// Driver code
// Array in which pair
// with max GCD is to
// be found
$arr = array( 1, 2, 4, 8, 8, 12 );
// Size of array
$n = sizeof($arr);
echo findMaxGCD($arr,$n);
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript Code for Find pair with
// maximum GCD in an array
// function to find GCD of pair with
// max GCD in the array
function findMaxGCD(arr , n)
{
// Computing highest element
var high = 0;
for (var i = 0; i < n; i++)
high = Math.max(high, arr[i]);
// Array to store the count of divisors
// i.e. Potential GCDs
var divisors =
Array.from({length: high + 1}, (_, i) => 0);
// Iterating over every element
for (var i = 0; i < n; i++)
{
// Calculating all the divisors
for (var j = 1; j <= Math.sqrt(arr[i]); j++)
{
// Divisor found
if (arr[i] % j == 0)
{
// Incrementing count for divisor
divisors[j]++;
// Element/divisor is also a divisor
// Checking if both divisors are
// not same
if (j != arr[i] / j)
divisors[arr[i] / j]++;
}
}
}
// Checking the highest potential GCD
for (var i = high; i >= 1; i--)
// If this divisor can divide at least 2
// numbers, it is a GCD of at least 1 pair
if (divisors[i] > 1)
return i;
return 1;
}
/* Driver program to test above function */
// Array in which pair with max GCD
// is to be found
var arr = [ 1, 2, 4, 8, 8, 12 ];
// Size of array
var n = arr.length;
document.write(findMaxGCD(arr,n));
// This code contributed by shikhasingrajput
</script>
Producción:
8
Complejidad de tiempo : O(N * sqrt(arr[i]) + H), donde arr[i] denota el elemento de la array y H denota el mayor número de la array.
Espacio auxiliar: O (alto), alto es el elemento máximo en la array
Método 3 (más eficiente) : este enfoque se basa en la idea de Tamiz de Eratóstenes .
Primero resolvamos un problema más simple, dado un valor X, tenemos que decir si un par tiene un MCD igual a X. Esto se puede hacer verificando cuántos elementos en la array son múltiplos de X. Si el número de tales múltiplos es mayor que 1, entonces X será un MCD de algún par.
Ahora, para emparejar con GCD máximo, mantenemos una array de conteo de la array original. Nuestro método se basa en el problema anterior con un enfoque similar a un tamiz para bucle. A continuación se muestra el algoritmo paso a paso de este enfoque:
- Iterar ‘i’ de MAX (elemento de array máximo) a 1.
- Iterar ‘j’ desde ‘i’ hasta MAX. Verificaremos si la array de conteo es 1 en el índice ‘j’.
- Incremente el índice ‘j’ cada vez con ‘i’. De esta forma, podemos verificar
i, 2i, 3i, etc. - Si obtenemos 1 dos veces en la array de conteo, eso significa que existen 2 múltiplos de i . Esto lo convierte en el GCD más alto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Code to
// Find pair with
// maximum GCD in
// an array
#include <bits/stdc++.h>
using namespace std;
// function to find
// GCD of pair with
// max GCD in the
// array
int findMaxGCD(int arr[], int n)
{
// Calculating MAX in array
int high = 0;
for (int i = 0; i < n; i++)
high = max(high, arr[i]);
// Maintaining count array
int count[high + 1] = {0};
for (int i = 0; i < n; i++)
count[arr[i]]++;
// Variable to store the
// multiples of a number
int counter = 0;
// Iterating from MAX to 1
// GCD is always between
// MAX and 1. The first
// GCD found will be the
// highest as we are
// decrementing the potential
// GCD
for (int i = high; i >= 1; i--)
{
int j = i;
counter = 0;
// Iterating from current
// potential GCD
// till it is less than
// MAX
while (j <= high)
{
// A multiple found
if(count[j] >=2)
return j;
else if (count[j] == 1)
counter++;
// Incrementing potential
// GCD by itself
// To check i, 2i, 3i....
j += i;
// 2 multiples found,
// max GCD found
if (counter == 2)
return i;
}
}
}
// Driver code
int main()
{
// Array in which pair
// with max GCD is to
// be found
int arr[] = { 1, 2, 4, 8, 8, 12 };
// Size of array
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMaxGCD(arr, n);
return 0;
}
Java
// Java Code to
// Find pair with
// maximum GCD in
// an array
class GFG {
// function to find
// GCD of pair with
// max GCD in the
// array
public static int findMaxGCD(int arr[], int n)
{
// Calculating MAX in
// array
int high = 0;
for (int i = 0; i < n; i++)
high = Math.max(high, arr[i]);
// Maintaining count array
int count[]=new int[high + 1];
for (int i = 0; i < n; i++)
count[arr[i]]++;
// Variable to store
// the multiples of
// a number
int counter = 0;
// Iterating from MAX
// to 1 GCD is always
// between MAX and 1
// The first GCD found
// will be the highest
// as we are decrementing
// the potential GCD
for (int i = high; i >= 1; i--)
{
int j = i;
// Iterating from current
// potential GCD till it
// is less than MAX
while (j <= high)
{
// A multiple found
if (count[j]>0)
counter+=count[j];
// Incrementing potential
// GCD by itself
// To check i, 2i, 3i....
j += i;
// 2 multiples found,
// max GCD found
if (counter == 2)
return i;
}
counter=0;
}
return 1;
}
/* Driver program to test above function */
public static void main(String[] args)
{
// Array in which pair
// with max GCD is to
// be found
int arr[] = {1, 2, 4, 8, 8, 12};
// Size of array
int n = arr.length;
System.out.println(findMaxGCD(arr,n));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 Code to # Find pair with # maximum GCD in # an array # function to find # GCD of pair with # max GCD in the # array def findMaxGCD(arr, n) : # Calculating MAX in # array high = 0 for i in range(0, n) : high = max(high, arr[i]) # Maintaining count array count = [0] * (high + 1) for i in range(0, n) : count[arr[i]]+=1 # Variable to store the # multiples of a number counter = 0 # Iterating from MAX # to 1 GCD is always # between MAX and 1 # The first GCD found # will be the highest # as we are decrementing # the potential GCD for i in range(high, 0, -1) : j = i # Iterating from current # potential GCD till it # is less than MAX while (j <= high) : # A multiple found if (count[j] >0) : counter+=count[j] # Incrementing potential # GCD by itself # To check i, 2i, 3i.... j += i # 2 multiples found, # max GCD found if (counter == 2) : return i counter=0 # Driver code # Array in which pair # with max GCD is to # be found arr = [1, 2, 4, 8, 8, 12] # Size of array n = len(arr) print(findMaxGCD(arr, n)) #This code is contributed by Nikita Tiwari.
C#
// C# Code to find pair with
// maximum GCD in an array
using System;
class GFG {
// function to find GCD
// of pair with max
// max GCD in the array
public static int findMaxGCD(int []arr,
int n)
{
// Calculating Max
// in array
int high = 0;
for (int i = 0; i < n; i++)
high = Math.Max(high, arr[i]);
// Maintaining count array
int []count=new int[high + 1];
for (int i = 0; i < n; i++)
count[arr[i]]++;
// Variable to store
// the multiples of
// a number
int counter = 0;
// Iterating from MAX
// to 1 GCD is always
// between MAX and 1
// The first GCD found
// will be the highest
// as we are decrementing
// the potential GCD
for (int i = high; i >= 1; i--)
{
int j = i;
// Iterating from current
// potential GCD till it
// is less than MAX
while (j <= high)
{
// A multiple found
if (count[j]>0)
counter+=count[j];
// Incrementing potential
// GCD by itself
// To check i, 2i, 3i....
j += i;
// 2 multiples found,
// max GCD found
if (counter == 2)
return i;
}
counter=0;
}
return 1;
}
// Driver Code
public static void Main(String []args)
{
// Array in which pair
// with max GCD is to
// be found
int []arr = {1, 2, 4, 8, 8, 12};
// Size of array
int n = arr.Length;
Console.WriteLine(findMaxGCD(arr,n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP Code to Find pair with maximum
// GCD in an array
// function to find GCD of pair with
// max GCD in the array
function findMaxGCD($arr, $n)
{
// Calculating MAX in array
$high = 0;
for ($i = 0; $i < $n; $i++)
$high = max($high, $arr[$i]);
// Maintaining count array
$count = array_fill(0, $high + 1, 0);
for ($i = 0; $i < $n; $i++)
$count[$arr[$i]]++;
// Variable to store the multiples
// of a number
$counter = 0;
// Iterating from MAX to 1 GCD is always
// between MAX and 1. The first GCD found
// will be the highest as we are decrementing
// the potential GCD
for ($i = $high; $i >= 1; $i--)
{
$j = $i;
$counter = 0;
// Iterating from current potential GCD
// till it is less than MAX
while ($j <= $high)
{
// A multiple found
if($count[$j] >= 2)
return $j;
else if ($count[$j] == 1)
$counter++;
// Incrementing potential GCD by itself
// To check i, 2i, 3i....
$j += $i;
// 2 multiples found, max GCD found
if ($counter == 2)
return $i;
}
}
}
// Driver code
// Array in which pair with max GCD
// is to be found
$arr = array( 1, 2, 4, 8, 8, 12 );
// Size of array
$n = count($arr);
print(findMaxGCD($arr, $n));
// This code is contributed by mits
?>
Javascript
<script>
// javascript Code to
// Find pair with
// maximum GCD in
// an array
// function to find
// GCD of pair with
// max GCD in the
// array
function findMaxGCD(arr , n)
{
// Calculating MAX in
// array
var high = 0;
for (let i = 0; i < n; i++)
high = Math.max(high, arr[i]);
// Maintaining count array
var count = Array(high + 1).fill(0);
for (let i = 0; i < n; i++)
count[arr[i]]++;
// Variable to store
// the multiples of
// a number
var counter = 0;
// Iterating from MAX
// to 1 GCD is always
// between MAX and 1
// The first GCD found
// will be the highest
// as we are decrementing
// the potential GCD
for (let i = high; i >= 1; i--)
{
var j = i;
// Iterating from current
// potential GCD till it
// is less than MAX
while (j <= high)
{
// A multiple found
if (count[j] > 0)
counter += count[j];
// Incrementing potential
// GCD by itself
// To check i, 2i, 3i....
j += i;
// 2 multiples found,
// max GCD found
if (counter == 2)
return i;
}
counter = 0;
}
return 1;
}
/* Driver program to test above function */
// Array in which pair
// with max GCD is to
// be found
var arr = [ 1, 2, 4, 8, 8, 12 ];
// Size of array
var n = arr.length;
document.write(findMaxGCD(arr, n));
// This code is contributed by aashish1995
</script>
Producción:
8
Complejidad del tiempo : La complejidad del tiempo de este enfoque es hasta un problema abierto conocido como el problema del divisor de Dirichlet.
Complejidad de tiempo: O (alto 2 ), alto es el elemento máximo en la array
Espacio auxiliar: O (alto), alto es el elemento máximo en la array
Este artículo es una contribución de Aarti_Rathi y Rohit Thapliyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA