Dados dos arreglos A[] y B[] que consisten en N enteros, la tarea es actualizar el arreglo A[] asignando cada elemento del arreglo A[i] a un solo elemento B[j] y actualizar A[i] a A[ i] + B[j] o A[i] * B[j] , tal que el producto de la array A[] se maximiza.
Nota: cada elemento de array en ambas arrays se puede emparejar con un solo elemento de la otra array solo una vez.
Ejemplos:
Entrada: A[] = {1, 1, 6}, B[] = {1, 2, 3}
Salida: 108
Explicación:
- Actualizar A[0] = A[0] + B[0], A[] se modifica a {2, 1, 6}
- Actualizar A[1] = A[1] + B[1], A[] se modifica a {2, 3, 6}
- Actualizar A[0] = A[0] * B[2], A[] se modifica a {6, 3, 6}
Por lo tanto, el producto del arreglo A[] es 6 * 3 * 6 = 108.
Entrada: A[] = {1, 1, 10}, B[] ={1, 1, 1}
Salida: 60
Explicación:
- Actualizar A[0] = A[0] + B[0], A[] se modifica a {2, 1, 10}
- Actualizar A[1] = A[1] + B[1], A[] se modifica a {2, 2, 10}
- Actualizar A[0] = A[0] * B[2], A[] se modifica a {3, 2, 10}
Enfoque: el problema anterior se puede resolver utilizando una cola de prioridad (min-heap) . Siga los pasos a continuación para resolver el problema:
- Ordene la array B[] .
- Inserte todos los elementos de la array A[] en la cola de prioridad para obtener el mínimo de elementos cada vez.
- Recorra la array dada B[] usando la variable j y saque un elemento de la cola de prioridad como el máximo de minE + B[j] o minE*B[j] y empuje este máximo a la cola de prioridad.
- Después de los pasos anteriores, el producto de los elementos en la cola de prioridad es el resultado requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the largest
// product of array A[]
int largeProduct(vector<int> A,
vector<int> B, int N)
{
// Base Case
if (N == 0)
return 0;
// Store all the elements of
// the array A[]
priority_queue<int, vector<int>,
greater<int>> pq;
for(int i = 0; i < N; i++)
pq.push(A[i]);
// Sort the Array B[]
sort(B.begin(), B.end());
// Traverse the array B[]
for(int i = 0; i < N; i++)
{
// Pop minimum element
int minn = pq.top();
pq.pop();
// Check which operation is
// producing maximum element
int maximized_element = max(minn * B[i],
minn + B[i]);
// Insert resultant element
// into the priority queue
pq.push(maximized_element);
}
// Evaluate the product
// of the elements of A[]
int max_product = 1;
while (pq.size() > 0)
{
max_product *= pq.top();
pq.pop();
}
// Return the maximum product
return max_product;
}
// Driver Code
int main()
{
// Given arrays
vector<int> A = { 1, 1, 10 };
vector<int> B = { 1, 1, 1 };
int N = 3;
// Function Call
cout << largeProduct(A, B, N);
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the largest
// product of array A[]
public static int largeProduct(
int A[], int B[], int N)
{
// Base Case
if (N == 0)
return 0;
// Store all the elements of
// the array A[]
PriorityQueue<Integer> pq
= new PriorityQueue<>();
for (int i = 0; i < N; i++)
pq.add(A[i]);
// Sort the Array B[]
Arrays.sort(B);
// Traverse the array B[]
for (int i = 0; i < N; i++) {
// Pop minimum element
int minn = pq.poll();
// Check which operation is
// producing maximum element
int maximized_element
= Math.max(minn * B[i],
minn + B[i]);
// Insert resultant element
// into the priority queue
pq.add(maximized_element);
}
// Evaluate the product
// of the elements of A[]
int max_product = 1;
while (pq.size() > 0) {
max_product *= pq.poll();
}
// Return the maximum product
return max_product;
}
// Driver Code
public static void main(String[] args)
{
// Given arrays
int A[] = { 1, 1, 10 };
int B[] = { 1, 1, 1 };
int N = 3;
// Function Call
System.out.println(
largeProduct(A, B, N));
}
}
Python3
# Python program for the above approach # Function to find the largest # product of array A[] def largeProduct(A, B, N): # Base Case if(N == 0): return 0 # Store all the elements of # the array A[] pq = [] for i in range(N): pq.append(A[i]) # Sort the Array B[] B.sort() pq.sort(reverse = True) # Traverse the array B[] for i in range(N): # Pop minimum element minn = pq.pop() # Check which operation is # producing maximum element maximized_element = max(minn * B[i], minn + B[i]) # Insert resultant element # into the priority queue pq.append(maximized_element) pq.sort(reverse = True) # Evaluate the product # of the elements of A[] max_product = 1 while(len(pq) > 0): max_product *= pq.pop(); # Return the maximum product return max_product # Driver Code # Given arrays A = [1, 1, 10] B = [1, 1, 1] N = 3 # Function Call print(largeProduct(A, B, N)) # This code is contributed by avanitrachhadiya2155
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the largest
// product of array A[]
public static int largeProduct(int[] A, int[] B, int N)
{
// Base Case
if(N == 0)
{
return 0;
}
// Store all the elements of
// the array A[]
List<int> pq = new List<int>();
for(int i = 0; i < N; i++)
{
pq.Add(A[i]);
}
// Sort the Array B[]
Array.Sort(B);
pq.Sort();
// Traverse the array B[]
for(int i = 0; i < N; i++)
{
int min = pq[0];
// Pop minimum element
pq.RemoveAt(0);
// Check which operation is
// producing maximum element
int maximized_element = Math.Max(min* B[i], min + B[i]);
// Insert resultant element
// into the priority queue
pq.Add(maximized_element);
pq.Sort();
}
// Evaluate the product
// of the elements of A[]
int max_product = 1;
while(pq.Count > 0)
{
max_product *= pq[0];
pq.RemoveAt(0);
}
// Return the maximum product
return max_product;
}
// Driver Code
static public void Main ()
{
// Given arrays
int[] A = { 1, 1, 10 };
int[] B = { 1, 1, 1 };
int N = 3;
// Function Call
Console.WriteLine(largeProduct(A, B, N));
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript program for the above approach
// Function to find the largest
// product of array A[]
function largeProduct(A, B, N)
{
// Base Case
if (N == 0)
return 0;
// Store all the elements of
// the array A[]
let pq=[];
for (let i = 0; i < N; i++)
pq.push(A[i]);
pq.sort(function(a,b){return a-b;});
// Sort the Array B[]
B.sort(function(a,b){return a-b;});
// Traverse the array B[]
for (let i = 0; i < N; i++) {
// Pop minimum element
let minn = pq.shift();
// Check which operation is
// producing maximum element
let maximized_element
= Math.max(minn * B[i],
minn + B[i]);
// Insert resultant element
// into the priority queue
pq.push(maximized_element);
pq.sort(function(a,b){return a-b;});
}
// Evaluate the product
// of the elements of A[]
let max_product = 1;
while (pq.length > 0) {
max_product *= pq.shift();
}
// Return the maximum product
return max_product;
}
// Driver Code
let A=[1, 1, 10 ];
let B=[1, 1, 1];
let N = 3;
document.write(largeProduct(A, B, N));
// This code is contributed by patel2127
</script>
Producción:
60
Complejidad temporal: O(N log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA