Dadas dos arrays de n enteros con valores de la array que son pequeños (los valores nunca exceden un número pequeño, digamos 100). Encuentre el par (x, y) que tiene mcd máximo . x e y no pueden ser de la misma array. Si varios pares tienen el mismo mcd, considere el par que tiene la suma máxima.
Ejemplos:
Input : a[] = {3, 1, 4, 2, 8}
b[] = {5, 2, 12, 8, 3}
Output : 8 8
Explanation: The maximum gcd is 8 which is
of pair(8, 8).
Input: a[] = {2, 3, 5}
b[] = {7, 11, 13}
Output: 5 13
Explanation: Every pair has a gcd of 1.
The maximum sum pair with GCD 1 is (5, 13)
Un enfoque ingenuo será iterar para cada par en ambas arrays y encontrar el gcd máximo posible.
Una forma eficiente (solo cuando los elementos son pequeños) es aplicar la propiedad tamiz y para eso necesitamos calcular previamente lo siguiente.
- Una array cnt para marcar la presencia de elementos de la array.
- Verificamos todos los números del 1 al N y para cada múltiplo, verificamos que si el número existe, se almacena el máximo del número preexistente o el actual múltiplo existente.
- Los pasos 1 y 2 también se repiten para la otra array.
- Al final, verificamos el múltiplo máximo que es común tanto en la primera como en la segunda array para obtener el GCD máximo, y en la posición de se almacena el elemento, primero se almacena el elemento de una array y en segundo el elemento de b array está almacenada, por lo que imprimimos el par.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP program to find maximum GCD pair
// from two arrays
#include <bits/stdc++.h>
using namespace std;
// Find the maximum GCD pair with maximum
// sum
void gcdMax(int a[], int b[], int n, int N)
{
// array to keep a count of existing elements
int cnt[N] = { 0 };
// first[i] and second[i] are going to store
// maximum multiples of i in a[] and b[]
// respectively.
int first[N] = { 0 }, second[N] = { 0 };
// traverse through the first array to
// mark the elements in cnt
for (int i = 0; i < n; ++i)
cnt[a[i]] = 1;
// Find maximum multiple of every number
// in first array
for (int i = 1; i < N; ++i)
for (int j = i; j < N; j += i)
if (cnt[j])
first[i] = max(first[i], j);
// Find maximum multiple of every number
// in second array
// We re-initialise cnt[] and traverse
// through the second array to mark the
// elements in cnt
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n; ++i)
cnt[b[i]] = true;
for (int i = 1; i < N; ++i)
for (int j = i; j < N; j += i)
// if the multiple is present in the
// second array then store the max
// of number or the pre-existing
// element
if (cnt[j])
second[i] = max(second[i], j);
// traverse for every elements and checks
// the maximum N that is present in both
// the arrays
int i;
for (i = N - 1; i >= 0; i--)
if (first[i] && second[i])
break;
cout << "Maximum GCD pair with maximum "
"sum is " << first[i] << " "
<< second[i] << endl;
}
// driver program to test the above function
int main()
{
int a[] = { 3, 1, 4, 2, 8 };
int b[] = { 5, 2, 12, 8, 3 };
int n = sizeof(a) / sizeof(a[0]);
// Maximum possible value of elements
// in both arrays.
int N = 20;
gcdMax(a, b, n, N);
return 0;
}
Java
// Java program to find maximum
// GCD pair from two arrays
class GFG
{
// Find the maximum GCD
// pair with maximum sum
static void gcdMax(int[] a, int[] b,
int n, int N)
{
// array to keep a count
// of existing elements
int[] cnt = new int[N];
// first[i] and second[i]
// are going to store
// maximum multiples of
// i in a[] and b[]
// respectively.
int[] first = new int[N];
int[] second = new int[N];
// traverse through the
// first array to mark
// the elements in cnt
for (int i = 0; i < n; ++i)
cnt[a[i]] = 1;
// Find maximum multiple
// of every number in
// first array
for (int i = 1; i < N; ++i)
for (int j = i; j < N; j += i)
if (cnt[j] > 0)
first[i] = Math.max(first[i], j);
// Find maximum multiple
// of every number in second
// array. We re-initialise
// cnt[] and traverse through
// the second array to mark
// the elements in cnt
cnt = new int[N];
for (int i = 0; i < n; ++i)
cnt[b[i]] = 1;
for (int i = 1; i < N; ++i)
for (int j = i; j < N; j += i)
// if the multiple is present
// in the second array then
// store the max of number or
// the pre-existing element
if (cnt[j] > 0)
second[i] = Math.max(second[i], j);
// traverse for every
// elements and checks
// the maximum N that
// is present in both
// the arrays
int x;
for (x = N - 1; x >= 0; x--)
if (first[x] > 0 &&
second[x] > 0)
break;
System.out.println(first[x] + " " +
second[x]);
}
// Driver Code
public static void main(String[] args)
{
int[] a = { 3, 1, 4, 2, 8 };
int[] b = { 5, 2, 12, 8, 3 };
int n = a.length;
// Maximum possible
// value of elements
// in both arrays.
int N = 20;
gcdMax(a, b, n, N);
}
}
// This code is contributed
// by mits
Python3
# Python 3 program to find maximum GCD pair # from two arrays # Find the maximum GCD pair with maximum # sum def gcdMax(a, b, n, N): # array to keep a count of existing elements cnt = [0]*N # first[i] and second[i] are going to store # maximum multiples of i in a[] and b[] # respectively. first = [0]*N second = [0]*N # traverse through the first array to # mark the elements in cnt for i in range(n): cnt[a[i]] = 1 # Find maximum multiple of every number # in first array for i in range(1,N): for j in range(i,N,i): if (cnt[j]): first[i] = max(first[i], j) # Find maximum multiple of every number # in second array # We re-initialise cnt[] and traverse # through the second array to mark the # elements in cnt cnt = [0]*N for i in range(n): cnt[b[i]] = 1 for i in range(1,N): for j in range(i,N,i): # if the multiple is present in the # second array then store the max # of number or the pre-existing # element if (cnt[j]>0): second[i] = max(second[i], j) # traverse for every elements and checks # the maximum N that is present in both # the arrays i = N-1 while i>= 0: if (first[i]>0 and second[i]>0): break i -= 1 print( str(first[i]) + " " + str(second[i])) # driver program to test the above function if __name__ == "__main__": a = [ 3, 1, 4, 2, 8 ] b = [ 5, 2, 12, 8, 3 ] n = len(a) # Maximum possible value of elements # in both arrays. N = 20 gcdMax(a, b, n, N) # this code is contributed by ChitraNayal
C#
// C# program to find
// maximum GCD pair
// from two arrays
using System;
class GFG
{
// Find the maximum GCD
// pair with maximum sum
static void gcdMax(int[] a, int[] b,
int n, int N)
{
// array to keep a count
// of existing elements
int[] cnt = new int[N];
// first[i] and second[i]
// are going to store
// maximum multiples of
// i in a[] and b[]
// respectively.
int[] first = new int[N];
int[] second = new int[N];
// traverse through the
// first array to mark
// the elements in cnt
for (int i = 0; i < n; ++i)
cnt[a[i]] = 1;
// Find maximum multiple
// of every number in
// first array
for (int i = 1; i < N; ++i)
for (int j = i; j < N; j += i)
if (cnt[j] > 0)
first[i] = Math.Max(first[i], j);
// Find maximum multiple
// of every number in second
// array. We re-initialise
// cnt[] and traverse through
// the second array to mark
// the elements in cnt
cnt = new int[N];
for (int i = 0; i < n; ++i)
cnt[b[i]] = 1;
for (int i = 1; i < N; ++i)
for (int j = i; j < N; j += i)
// if the multiple is present
// in the second array then
// store the max of number or
// the pre-existing element
if (cnt[j] > 0)
second[i] = Math.Max(second[i], j);
// traverse for every
// elements and checks
// the maximum N that
// is present in both
// the arrays
int x;
for (x = N - 1; x >= 0; x--)
if (first[x] > 0 &&
second[x] > 0)
break;
Console.WriteLine(first[x] +
" " + second[x]);
}
// Driver Code
static int Main()
{
int[] a = { 3, 1, 4, 2, 8 };
int[] b = { 5, 2, 12, 8, 3 };
int n = a.Length;
// Maximum possible
// value of elements
// in both arrays.
int N = 20;
gcdMax(a, b, n, N);
return 0;
}
}
// This code is contributed
// by mits
PHP
<?php
// PHP program to find
// maximum GCD pair
// from two arrays
// Find the maximum GCD
// pair with maximum
// sum
function gcdMax($a, $b, $n, $N)
{
// array to keep a count
// of existing elements
$cnt = array_fill(0, $N, 0);
// first[i] and second[i] are
// going to store maximum
// multiples of i in a[] and
// b[] respectively.
$first = array_fill(0, $N, 0);
$second = array_fill(0, $N, 0);
// traverse through the first
// array to mark the elements
// in cnt
for ($i = 0; $i < $n; ++$i)
$cnt[$a[$i]] = 1;
// Find maximum multiple
// of every number in
// first array
for ($i = 1; $i < $N; ++$i)
for ($j = $i; $j < $N; $j += $i)
if ($cnt[$j])
$first[$i] = max($first[$i], $j);
// Find maximum multiple of every
// number in second array
// We re-initialise cnt[] and
// traverse through the second
// array to mark the elements in cnt
$cnt = array_fill(0, $N, 0);
for ($i = 0; $i < $n; $i++)
$cnt[$b[$i]] = 1;
for ($i = 1; $i < $N; $i++)
for ($j = $i; $j < $N; $j += $i)
// if the multiple is present
// in the second array then
// store the max of number or
// the pre-existing element
if ($cnt[$j])
$second[$i] = max($second[$i], $j);
// traverse for every elements
// and checks the maximum N
// that is present in both
// the arrays
$x = $N - 1;
for (; $x >= 0; $x--)
if ($first[$x] && $second[$x])
break;
echo $first[$x] . " " .
$second[$x] . "\n";
}
// Driver code
$a = array(3, 1, 4, 2, 8);
$b = array(5, 2, 12, 8, 3);
$n = sizeof($a);
// Maximum possible value
// of elements in both arrays.
$N = 20;
gcdMax($a, $b, $n, $N);
// This code is contributed
// by mits
?>
Javascript
<script>
// Javascript program to find maximum
// GCD pair from two arrays
// Find the maximum GCD
// pair with maximum sum
function gcdMax(a, b, n, N)
{
// array to keep a count
// of existing elements
let cnt = Array.from({length: N},
(_, i) => 0);
// first[i] and second[i]
// are going to store
// maximum multiples of
// i in a[] and b[]
// respectively.
let first = Array.from({length: N}, (_, i) => 0);
let second = Array.from({length: N}, (_, i) => 0);
// traverse through the
// first array to mark
// the elements in cnt
for (let i = 0; i < n; ++i)
cnt[a[i]] = 1;
// Find maximum multiple
// of every number in
// first array
for (let i = 1; i < N; ++i)
for (let j = i; j < N; j += i)
if (cnt[j] > 0)
first[i] = Math.max(first[i], j);
// Find maximum multiple
// of every number in second
// array. We re-initialise
// cnt[] and traverse through
// the second array to mark
// the elements in cnt
cnt = Array.from({length: N}, (_, i) => 0);
for (let i = 0; i < n; ++i)
cnt[b[i]] = 1;
for (let i = 1; i < N; ++i)
for (let j = i; j < N; j += i)
// if the multiple is present
// in the second array then
// store the max of number or
// the pre-existing element
if (cnt[j] > 0)
second[i] = Math.max(second[i], j);
// traverse for every
// elements and checks
// the maximum N that
// is present in both
// the arrays
let x;
for (x = N - 1; x >= 0; x--)
if (first[x] > 0 &&
second[x] > 0)
break;
document.write(first[x] + " " +
second[x]);
}
// driver program
let a = [ 3, 1, 4, 2, 8 ];
let b = [ 5, 2, 12, 8, 3 ];
let n = a.length;
// Maximum possible
// value of elements
// in both arrays.
let N = 20;
gcdMax(a, b, n, N);
</script>
Producción :
8 8
Complejidad de tiempo: O(N Log N + N), ya que estamos usando bucles anidados donde el bucle exterior atraviesa N veces y el bucle interior atraviesa logN veces (como N + (N/2) + (N/3) + ….. + 1 = N log N) y estamos usando Loop adicional para atravesar N veces.
Espacio auxiliar: O (N), ya que estamos usando espacio adicional para la array cnt.
Este artículo es una contribución de Raj . 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