Dadas dos arrays enteras arr[] y cost[] donde cost[i] es el costo de elegir arr[i] . La tarea es elegir un subconjunto con al menos dos elementos, de modo que el MCD de todos los elementos del subconjunto sea 1 y el costo de elegir esos elementos sea el mínimo posible, luego imprima el costo mínimo.
Ejemplos:
Entrada: arr[] = {5, 10, 12, 1}, costo[] = {2, 1, 2, 6}
Salida: 4
{5, 12} es el subconjunto requerido con costo = 2 + 2 = 4
Entrada : arr[] = {50, 100, 150, 200, 300}, cost[] = {2, 3, 4, 5, 6} Salida: -1 No es posible subconjunto
con gcd
= 1
Enfoque: agregue GCD de dos elementos cualquiera a un mapa, ahora para cada elemento arr[i] calcule su gcd con todos los valores de gcd encontrados hasta ahora (guardados en el mapa) y actualice map[gcd] = min(map[gcd] , mapa[mcd] + costo[i]) . Si al final, el mapa no contiene ninguna entrada para gcd = 1 , imprima -1; de lo contrario, imprima el costo mínimo almacenado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum cost required
int getMinCost(int arr[], int n, int cost[])
{
// Map to store <gcd, cost> pair where
// cost is the cost to get the current gcd
map<int, int> mp;
mp.clear();
mp[0] = 0;
for (int i = 0; i < n; i++) {
for (auto it : mp) {
int gcd = __gcd(arr[i], it.first);
// If current gcd value already exists in map
if (mp.count(gcd) == 1)
// Update the minimum cost
// to get the current gcd
mp[gcd] = min(mp[gcd], it.second + cost[i]);
else
mp[gcd] = it.second + cost[i];
}
}
// If there can be no sub-set such that
// the gcd of all the elements is 1
if (mp[1] == 0)
return -1;
else
return mp[1];
}
// Driver code
int main()
{
int arr[] = { 5, 10, 12, 1 };
int cost[] = { 2, 1, 2, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << getMinCost(arr, n, cost);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
class GFG{
// Function to return the minimum cost required
static int getMinCost(int arr[], int n, int cost[])
{
// Map to store <gcd, cost> pair where
// cost is the cost to get the current gcd
Map<Integer,Integer> mp = new ConcurrentHashMap<Integer,Integer>();
mp.clear();
mp.put(0, 0);
for (int i = 0; i < n; i++) {
for (Map.Entry<Integer,Integer> it : mp.entrySet()){
int gcd = __gcd(arr[i], it.getKey());
// If current gcd value already exists in map
if (mp.containsKey(gcd))
// Update the minimum cost
// to get the current gcd
mp.put(gcd, Math.min(mp.get(gcd), it.getValue() + cost[i]));
else
mp.put(gcd,it.getValue() + cost[i]);
}
}
// If there can be no sub-set such that
// the gcd of all the elements is 1
if (!mp.containsKey(1))
return -1;
else
return mp.get(1);
}
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, 10, 12, 1 };
int cost[] = { 2, 1, 2, 6 };
int n = arr.length;
System.out.print(getMinCost(arr, n, cost));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the approach from math import gcd as __gcd # Function to return the minimum cost required def getMinCost(arr, n, cost): # Map to store <gcd, cost> pair where # cost is the cost to get the current gcd mp = dict() mp[0] = 0 for i in range(n): for it in list(mp): gcd = __gcd(arr[i], it) # If current gcd value # already exists in map if (gcd in mp): # Update the minimum cost # to get the current gcd mp[gcd] = min(mp[gcd], mp[it] + cost[i]) else: mp[gcd] = mp[it] + cost[i] # If there can be no sub-set such that # the gcd of all the elements is 1 if (mp[1] == 0): return -1 else: return mp[1] # Driver code arr = [ 5, 10, 12, 1] cost = [ 2, 1, 2, 6] n = len(arr) print(getMinCost(arr, n, cost)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG
{
static int __gcd(int a, int b)
{
return b == 0? a:__gcd(b, a % b);
}
// Function to return the minimum cost required
static int getMinCost(int[] arr, int n, int[] cost)
{
// Map to store <gcd, cost> pair where
// cost is the cost to get the current gcd
Dictionary<int, int> mp = new Dictionary<int, int>();
mp.Add(0, 0);
for (int i = 0; i < n; i++)
{
foreach (int it in mp.Keys.ToList())
{
int gcd = __gcd(arr[i], it);
// If current gcd value already exists in map
if(mp.ContainsKey(gcd))
{
// Update the minimum cost
// to get the current gcd
mp[gcd] = Math.Min(mp[gcd], mp[it] + cost[i]);
}
else
{
mp.Add(gcd, mp[it] + cost[i]);
}
}
}
// If there can be no sub-set such that
// the gcd of all the elements is 1
if (mp[1] == 0)
{
return -1;
}
else
{
return mp[1];
}
}
// Driver code
static public void Main ()
{
int[] arr = { 5, 10, 12, 1 };
int[] cost = { 2, 1, 2, 6 };
int n = arr.Length;
Console.WriteLine(getMinCost(arr, n, cost));
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the minimum cost required
function getMinCost(arr,n,cost)
{
// Map to store <gcd, cost> pair where
// cost is the cost to get the current gcd
let mp = new Map();
mp.set(0, 0);
for (let i = 0; i < n; i++) {
for (let [key, value] of mp.entries()){
let gcd = __gcd(arr[i], key);
// If current gcd value already exists in map
if (mp.has(gcd))
// Update the minimum cost
// to get the current gcd
mp.set(gcd, Math.min(mp.get(gcd), value + cost[i]));
else
mp.set(gcd,value + cost[i]);
}
}
// If there can be no sub-set such that
// the gcd of all the elements is 1
if (!mp.has(1))
return -1;
else
return mp.get(1);
}
function __gcd(a,b)
{
return b == 0? a:__gcd(b, a % b);
}
// Driver code
let arr=[5, 10, 12, 1 ];
let cost=[2, 1, 2, 6 ];
let n = arr.length;
document.write(getMinCost(arr, n, cost));
// This code is contributed by unknown2108
</script>
Producción:
4
Complejidad temporal: O(n 2 log(n)) donde n es el número de elementos.
Espacio Auxiliar: O(n)