Dada una array arr[] de enteros positivos de tamaño N , la tarea es dividir la array en dos subconjuntos no vacíos X e Y de tal manera que la suma de su GCD resulte ser la máxima posible
Ejemplos:
Entrada: N = 3, arr[] = {1, 2, 9}
Salida: 10
Explicación: Podemos dividir la array como
X = (1, 2) con MCD = 1
Y = (9) con MCD = 9
Suma máxima viene como 10Entrada: N = 4, arr[] = {7, 21, 27, 28}
Salida: 34
Explicación: Posibles divisiones:
X= 7, 21, 28 con MCD = 7 e Y = 27 con MCD =27. Suma = 34
X = 7, 21, 27 con MCD = 1 y Y = 28 con MCD =28. Suma = 29
Use la primera forma para la suma máxima posible, es decir, 34.
Planteamiento: El problema se puede resolver a partir de la siguiente idea:
Para obtener la suma máxima de GCD, mantenga el más alto en un subconjunto (digamos X ) y los demás en otro (digamos Y ).
Pero puede dar lugar a un caso en el que el segundo elemento único máximo cause el GCD de Y = 1 pero el elemento máximo cuando se considera en Y y el segundo máximo en X, entonces la suma de GCD puede ser mayor. (Ocurre cuando el elemento máximo cuando se mantiene con elementos del subconjunto Y, el GCD es mayor que 1, pero cuando el segundo más grande estaba en Y, era 1).
No necesitamos considerar el 3er más grande porque si tanto el primero como el segundo más grande son divisibles por el MCD, entonces la diferencia es mayor que el MCD[digamos a ] y el 3er más grande + a < 1 + el más grande como el más grande > el 3er más grande+a
- Entonces, para obtener la suma máxima de gcd, tomaremos gcd de los n-2 elementos únicos más pequeños.
- Encuentra incluyendo cuál da la suma mayor.
Siga los pasos a continuación para comprender mejor:
- Primero ordene la array arr[] .
- Atraviese arr desde i = 0 hasta i = N-1 y encuentre todos los elementos únicos.
- Si solo hubiera un elemento, entonces la división en subconjuntos no es posible.
- Si solo hay un elemento único pero más de una vez, entonces el mismo elemento estará presente en ambos subconjuntos.
- Si solo hay dos elementos únicos después de evitar las repeticiones, devuelva su suma.
- Tome mcd de todos los elementos excepto los dos últimos:
- Comprueba cuál es mejor mantener solo último o penúltimo elemento.
- Devuelve la suma máxima.
A continuación se muestra el código para la implementación anterior:
C++
// C++ code for above approach
#include <bits/stdc++.h>
using namespace std;
// Function for finding maximum value sum of
// GCD of Subsets
int SubMaxGCD(int N, vector<int>& A)
{
// If only one element
if (A.size() == 1)
return -1;
// Sort the given array
sort(A.begin(), A.end());
vector<int> v;
// Running till last-1 element
for (int i = 0; i < N - 1; ++i) {
// Avoiding repetitions
// as GCD remains same
if (A[i] == A[i + 1])
continue;
else
v.push_back(A[i]);
}
// Pushing the last element
// It avoids the case of
// all the same element
v.push_back(A[N - 1]);
if (v.size() == 1) {
// Returning if v.size is 1
// i.e. all elements are same
return v[0] * 2;
}
// Corner case if there are only two
// elements after avoiding repetitions
if (v.size() == 2) {
return v[0] + v[1];
}
int n = v.size();
int g = v[0];
// Taking gcd of all elements
// except last two elements
for (int i = 1; i < n - 2; ++i) {
g = __gcd(g, v[i]);
}
// Check which is better to keep alone
// last or second last element
int gcd_a = __gcd(g, v[n - 2]) + v[n - 1];
int gcd_b = __gcd(g, v[n - 1]) + v[n - 2];
// Return the maximum sum.
if (gcd_a >= gcd_b)
return gcd_a;
else
return gcd_b;
}
// Driver code
int main()
{
int N = 3;
vector<int> arr = { 1, 2, 9 };
// Function call
cout << SubMaxGCD(N, arr);
return 0;
}
Java
// Java code for above approach
import java.io.*;
import java.util.*;
class GFG {
public static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function for finding maximum value sum of
// GCD of Subsets
public static int SubMaxGCD(int N, int A[])
{
// If only one element
if (A.length == 1)
return -1;
// Sort the given array
Arrays.sort(A);
ArrayList<Integer> v = new ArrayList<>();
// Running till last-1 element
for (int i = 0; i < N - 1; ++i) {
// Avoiding repetitions
// as GCD remains same
if (A[i] == A[i + 1])
continue;
else
v.add(A[i]);
}
// Pushing the last element
// It avoids the case of
// all the same element
v.add(A[N - 1]);
if (v.size() == 1) {
// Returning if v.size is 1
// i.e. all elements are same
return v.get(0) * 2;
}
// Corner case if there are only two
// elements after avoiding repetitions
if (v.size() == 2) {
return v.get(0) + v.get(1);
}
int n = v.size();
int g = v.get(0);
// Taking gcd of all elements
// except last two elements
for (int i = 1; i < n - 2; ++i) {
g = gcd(g, v.get(i));
}
// Check which is better to keep alone
// last or second last element
int gcd_a = gcd(g, v.get(n - 2)) + v.get(n - 1);
int gcd_b = gcd(g, v.get(n - 1)) + v.get(n - 2);
// Return the maximum sum.
if (gcd_a >= gcd_b)
return gcd_a;
else
return gcd_b;
}
// Driver Code
public static void main(String[] args)
{
int N = 3;
int arr[] = { 1, 2, 9 };
// Function call
System.out.print(SubMaxGCD(N, arr));
}
}
// This code is contributed by Rohit Pradhan
Python3
# python3 code for above approach def gcd( a, b) : if (b == 0) : return a return gcd(b, a % b) # Function for finding maximum value sum of # GCD of Subsets def SubMaxGCD( N, A) : # If only one element if len(A) == 1 : return -1 # Sort the given array A.sort() v=[] # Running till last-1 element for i in range(N-1) : # Avoiding repetitions # as GCD remains same if A[i] == A[i + 1] : continue else : v.append(A[i]) # Pushing the last element # It avoids the case of # all the same element v.append(A[N - 1]) if len(v) == 1 : # Returning if v.size is 1 # i.e. all elements are same return v[0] * 2 # Corner case if there are only two # elements after avoiding repetitions if len(v) == 2 : return v[0] + v[1] n = len(v) g = v[0] # Taking gcd of all elements # except last two elements for i in range(N-2): g = gcd(g, v[i]) # Check which is better to keep alone # last or second last element gcd_a = gcd(g, v[n - 2]) + v[n - 1] gcd_b = gcd(g, v[n - 1]) + v[n - 2] # Return the maximum sum. if gcd_a >= gcd_b : return gcd_a else : return gcd_b # Driver Code if __name__ == "__main__": N = 3 arr = [ 1, 2, 9 ] # Function call print(SubMaxGCD(N, arr)) # This code is contributed by jana_sayantan.
C#
// C# code for above approach
using System;
using System.Collections;
class GFG {
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function for finding maximum value sum of
// GCD of Subsets
static int SubMaxGCD(int N, int[] A)
{
// If only one element
if (A.Length == 1)
return -1;
// Sort the given array
Array.Sort(A);
ArrayList v = new ArrayList();
// Running till last-1 element
for (int i = 0; i < N - 1; ++i) {
// Avoiding repetitions
// as GCD remains same
if (A[i] == A[i + 1])
continue;
else
v.Add(A[i]);
}
// Pushing the last element
// It avoids the case of
// all the same element
v.Add(A[N - 1]);
if (v.Count == 1) {
// Returning if v.size is 1
// i.e. all elements are same
return (int)v[0] * 2;
}
// Corner case if there are only two
// elements after avoiding repetitions
if (v.Count == 2) {
return (int)v[0] + (int)v[1];
}
int n = v.Count;
int g = (int)v[0];
// Taking gcd of all elements
// except last two elements
for (int i = 1; i < n - 2; ++i) {
g = gcd(g, (int)v[i]);
}
// Check which is better to keep alone
// last or second last element
int gcd_a = gcd(g, (int)v[n - 2]) + (int)v[n - 1];
int gcd_b = gcd(g, (int)v[n - 1]) + (int)v[n - 2];
// Return the maximum sum.
if (gcd_a >= gcd_b)
return gcd_a;
else
return gcd_b;
}
// Driver Code
public static void Main()
{
int N = 3;
int[] arr = { 1, 2, 9 };
// Function call
Console.Write(SubMaxGCD(N, arr));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for above approach
// Function for GCD
const __gcd = (a, b) => {
if (b == 0) return a;
return __gcd(b, a % b);
}
// Function for finding maximum value sum of
// GCD of Subsets
const SubMaxGCD = (N, A) => {
// If only one element
if (A.length == 1)
return -1;
// Sort the given array
A.sort();
let v = [];
// Running till last-1 element
for (let i = 0; i < N - 1; ++i) {
// Avoiding repetitions
// as GCD remains same
if (A[i] == A[i + 1])
continue;
else
v.push(A[i]);
}
// Pushing the last element
// It avoids the case of
// all the same element
v.push(A[N - 1]);
if (v.length == 1) {
// Returning if v.size is 1
// i.e. all elements are same
return v[0] * 2;
}
// Corner case if there are only two
// elements after avoiding repetitions
if (v.length == 2) {
return v[0] + v[1];
}
let n = v.length;
let g = v[0];
// Taking gcd of all elements
// except last two elements
for (let i = 1; i < n - 2; ++i) {
g = __gcd(g, v[i]);
}
// Check which is better to keep alone
// last or second last element
let gcd_a = __gcd(g, v[n - 2]) + v[n - 1];
let gcd_b = __gcd(g, v[n - 1]) + v[n - 2];
// Return the maximum sum.
if (gcd_a >= gcd_b)
return gcd_a;
else
return gcd_b;
}
// Driver code
let N = 3;
let arr = [1, 2, 9];
// Function call
document.write(SubMaxGCD(N, arr));
// This code is contributed by rakeshsahni.
</script>
Producción
10
Complejidad temporal: O(N * logN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hemantrathore2705 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA