Dados dos arreglos de igual longitud A[] y B[] , que consisten solo en números enteros positivos, la tarea es invertir cualquier subarreglo del primer arreglo tal que la suma del producto de los elementos del mismo índice de los dos arreglos, es decir (A [i] * B[i]) es mínimo.
Ejemplos:
Entrada: N = 4, A[] = {2, 3, 1, 5}, B[] = {8, 2, 4, 3}
Salida:
A[] = 1 3 2 5
B[] = 8 2 4 3
El producto mínimo es 37Explicación: Invierta el subarreglo {A[0], A[2]}. La suma del producto de los mismos elementos indexados es 37, que es el mínimo posible.
Entrada: N = 3, A[] = {3, 1, 1}, B[] = {4, 5, 6}
Salida:
A[] = 3 1 1
B[] = 4 5 6
El producto mínimo es 23
Enfoque: el problema dado se puede resolver utilizando la técnica de dos punteros . Siga los pasos a continuación para resolver el problema:
- Declare una variable, digamos total , para almacenar el producto inicial de las dos arrays.
- Declare una variable, digamos min , para almacenar la respuesta requerida.
- Declare dos variables, digamos first y second , para almacenar los índices inicial y final del subarreglo que debe invertirse para minimizar el producto.
- Calcule el producto mínimo posible para subarreglos de longitud impar mediante las siguientes operaciones:
- Recorre la array usando una variable, digamos i .
- Compruebe todos los subarreglos de longitud impar, estableciendo i – 1 , digamos a la izquierda , e i + 1 , digamos a la derecha , como los índices inicial y final de los subarreglos.
- Actualice el total restando a[izquierda] * b[izquierda] + a[derecha] * b[derecha] y sumando a[izquierda] * b[derecha] + a[derecha] * b[izquierda].
- Para cada subarreglo, después de actualizar el total , verifique si es el mínimo obtenido o no. Actualice y almacene el producto mínimo en consecuencia.
- De manera similar, verifique todos los subarreglos de longitud par y calcule la suma.
- Finalmente, imprima las arrays y la suma mínima obtenida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to print1 the arrays
void print1(vector<int> &a, vector<int> &b)
{
int minProd = 0;
for(int i = 0; i < a.size(); ++i)
{
cout << a[i] << " ";
}
cout << endl;
for(int i = 0; i < b.size(); ++i)
{
cout << b[i] << " ";
minProd += a[i] * b[i];
}
cout << endl;
cout << minProd;
}
// Function to reverse1 the subarray
void reverse1(int left, int right,
vector<int> &arr)
{
while (left < right)
{
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
++left;
--right;
}
}
// Function to calculate the
// minimum product of same-indexed
// elements of two given arrays
void minimumProdArray(vector<int> &a,
vector<int> &b, int l)
{
int total = 0;
// Calculate initial product
for(int i = 0; i < a.size(); ++i)
{
total += a[i] * b[i];
}
int min = INT_MAX;
int first = 0;
int second = 0;
// Traverse all odd length subarrays
for(int i = 0; i < a.size(); ++i)
{
int left = i - 1;
int right = i + 1;
int total1 = total;
while (left >= 0 && right < a.size())
{
// Remove the previous product
total1 -= a[left] * b[left] +
a[right] * b[right];
// Add the current product
total1 += a[left] * b[right] +
a[right] * b[left];
// Check if current product
// is minimum or not
if (min >= total1)
{
min = total1;
first = left;
second = right;
}
--left;
++right;
}
}
// Traverse all even length subarrays
for(int i = 0; i < a.size(); ++i)
{
int left = i;
int right = i + 1;
int total1 = total;
while (left >= 0 && right < a.size())
{
// Remove the previous product
total1 -= a[left] * b[left] +
a[right] * b[right];
// Add to the current product
total1 += a[left] * b[right] +
a[right] * b[left];
// Check if current product
// is minimum or not
if (min >= total1)
{
min = total1;
first = left;
second = right;
}
// Update the pointers
--left;
++right;
}
}
// reverse1 the subarray
if (min < total)
{
reverse1(first, second, a);
// print1 the subarray
print1(a, b);
}
else
{
print1(a, b);
}
}
// Driver Code
int main()
{
int n = 4;
vector<int> a{ 2, 3, 1, 5 };
vector<int> b{ 8, 2, 4, 3 };
minimumProdArray(a, b, n);
}
// This code is contributed by bgangwar59
Java
// Java Program to implement the above approach
import java.io.*;
import java.util.*;
public class Main {
// Function to calculate the
// minimum product of same-indexed
// elements of two given arrays
static void minimumProdArray(long a[],
long b[], int l)
{
long total = 0;
// Calculate initial product
for (int i = 0; i < a.length; ++i) {
total += a[i] * b[i];
}
long min = Integer.MAX_VALUE;
int first = 0;
int second = 0;
// Traverse all odd length subarrays
for (int i = 0; i < a.length; ++i) {
int left = i - 1;
int right = i + 1;
long total1 = total;
while (left >= 0 && right < a.length) {
// Remove the previous product
total1 -= a[left] * b[left]
+ a[right] * b[right];
// Add the current product
total1 += a[left] * b[right]
+ a[right] * b[left];
// Check if current product
// is minimum or not
if (min >= total1) {
min = total1;
first = left;
second = right;
}
--left;
++right;
}
}
// Traverse all even length subarrays
for (int i = 0; i < a.length; ++i) {
int left = i;
int right = i + 1;
long total1 = total;
while (left >= 0 && right < a.length) {
// Remove the previous product
total1 -= a[left] * b[left]
+ a[right] * b[right];
// Add to the current product
total1 += a[left] * b[right]
+ a[right] * b[left];
// Check if current product
// is minimum or not
if (min >= total1) {
min = total1;
first = left;
second = right;
}
// Update the pointers
--left;
++right;
}
}
// Reverse the subarray
if (min < total) {
reverse(first, second, a);
// Print the subarray
print(a, b);
}
else {
print(a, b);
}
}
// Function to reverse the subarray
static void reverse(int left, int right,
long arr[])
{
while (left < right) {
long temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
++left;
--right;
}
}
// Function to print the arrays
static void print(long a[], long b[])
{
int minProd = 0;
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + " ");
}
System.out.println();
for (int i = 0; i < b.length; ++i) {
System.out.print(b[i] + " ");
minProd += a[i] * b[i];
}
System.out.println();
System.out.println(minProd);
}
// Driver Code
public static void main(String[] args)
{
int n = 4;
long a[] = { 2, 3, 1, 5 };
long b[] = { 8, 2, 4, 3 };
minimumProdArray(a, b, n);
}
}
Python3
# Python3 Program to implement the above approach # Function to calculate the # minimum product of same-indexed # elements of two given arrays def minimumProdArray(a, b, l) : total = 0 # Calculate initial product for i in range(len(a)): total += a[i] * b[i] Min = 2147483647 first = 0; second = 0; # Traverse all odd length subarrays for i in range(len(a)): left = i - 1; right = i + 1; total1 = total; while (left >= 0 and right < len(a)) : # Remove the previous product total1 -= a[left] * b[left] + a[right] * b[right]; # Add the current product total1 += a[left] * b[right] + a[right] * b[left]; # Check if current product # is minimum or not if (Min >= total1) : Min = total1 first = left second = right left -= 1 right += 1 # Traverse all even length subarrays for i in range(len(a)): left = i right = i + 1 total1 = total while (left >= 0 and right < len(a)) : # Remove the previous product total1 -= a[left] * b[left] + a[right] * b[right] # Add to the current product total1 += a[left] * b[right] + a[right] * b[left] # Check if current product # is minimum or not if (Min >= total1) : Min = total1 first = left second = right # Update the pointers left -= 1 right += 1 # Reverse the subarray if (Min < total) : reverse(first, second, a) # Print the subarray Print(a, b) else : Print(a, b) # Function to reverse the subarray def reverse(left, right, arr) : while (left < right) : temp = arr[left] arr[left] = arr[right] arr[right] = temp left += 1 right -= 1 # Function to print the arrays def Print(a, b): minProd = 0 for i in range(len(a)): print(a[i], end = " ") print(); for i in range(len(b)): print(b[i], end = " ") minProd += a[i] * b[i] print() print(minProd) n = 4; a = [ 2, 3, 1, 5 ] b = [ 8, 2, 4, 3 ] minimumProdArray(a, b, n) # This code is contributed by divyeshrabadiya07
C#
// C# Program to implement the above approach
using System;
public class GFG {
// Function to calculate the
// minimum product of same-indexed
// elements of two given arrays
static void minimumProdArray(long[] a, long[] b, int l)
{
long total = 0;
// Calculate initial product
for (int i = 0; i < a.Length; ++i) {
total += a[i] * b[i];
}
long min = Int32.MaxValue;
int first = 0;
int second = 0;
// Traverse all odd length subarrays
for (int i = 0; i < a.Length; ++i) {
int left = i - 1;
int right = i + 1;
long total1 = total;
while (left >= 0 && right < a.Length) {
// Remove the previous product
total1 -= a[left] * b[left]
+ a[right] * b[right];
// Add the current product
total1 += a[left] * b[right]
+ a[right] * b[left];
// Check if current product
// is minimum or not
if (min >= total1) {
min = total1;
first = left;
second = right;
}
--left;
++right;
}
}
// Traverse all even length subarrays
for (int i = 0; i < a.Length; ++i) {
int left = i;
int right = i + 1;
long total1 = total;
while (left >= 0 && right < a.Length) {
// Remove the previous product
total1 -= a[left] * b[left]
+ a[right] * b[right];
// Add to the current product
total1 += a[left] * b[right]
+ a[right] * b[left];
// Check if current product
// is minimum or not
if (min >= total1) {
min = total1;
first = left;
second = right;
}
// Update the pointers
--left;
++right;
}
}
// Reverse the subarray
if (min < total) {
reverse(first, second, a);
// Print the subarray
print(a, b);
}
else {
print(a, b);
}
}
// Function to reverse the subarray
static void reverse(int left, int right, long[] arr)
{
while (left < right) {
long temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
++left;
--right;
}
}
// Function to print the arrays
static void print(long[] a, long[] b)
{
long minProd = 0;
for (int i = 0; i < a.Length; ++i) {
Console.Write(a[i] + " ");
}
Console.WriteLine();
for (int i = 0; i < b.Length; ++i) {
Console.Write(b[i] + " ");
minProd += a[i] * b[i];
}
Console.WriteLine();
Console.WriteLine(minProd);
}
// Driver Code
public static void Main(string[] args)
{
int n = 4;
long[] a = { 2, 3, 1, 5 };
long[] b = { 8, 2, 4, 3 };
minimumProdArray(a, b, n);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript program to implement the above approach
// Function to print1 the arrays
function print1(a, b) {
let minProd = 0;
for (let i = 0; i < a.length; ++i) {
document.write(a[i] + " ");
}
document.write("<br>");
for (let i = 0; i < b.length; ++i) {
document.write(b[i] + " ");
minProd += a[i] * b[i];
}
document.write("<br>");
document.write(minProd);
}
// Function to reverse1 the subarray
function reverse1(left, right, arr) {
while (left < right) {
let temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
++left;
--right;
}
}
// Function to calculate the
// minimum product of same-indexed
// elements of two given arrays
function minimumProdArray(a, b, l) {
let total = 0;
// Calculate initial product
for (let i = 0; i < a.length; ++i) {
total += a[i] * b[i];
}
let min = Number.MAX_SAFE_INTEGER;
let first = 0;
let second = 0;
// Traverse all odd length subarrays
for (let i = 0; i < a.length; ++i) {
let left = i - 1;
let right = i + 1;
let total1 = total;
while (left >= 0 && right < a.length) {
// Remove the previous product
total1 -= a[left] * b[left] +
a[right] * b[right];
// Add the current product
total1 += a[left] * b[right] +
a[right] * b[left];
// Check if current product
// is minimum or not
if (min >= total1) {
min = total1;
first = left;
second = right;
}
--left;
++right;
}
}
// Traverse all even length subarrays
for (let i = 0; i < a.length; ++i) {
let left = i;
let right = i + 1;
let total1 = total;
while (left >= 0 && right < a.length) {
// Remove the previous product
total1 -= a[left] * b[left] +
a[right] * b[right];
// Add to the current product
total1 += a[left] * b[right] +
a[right] * b[left];
// Check if current product
// is minimum or not
if (min >= total1) {
min = total1;
first = left;
second = right;
}
// Update the pointers
--left;
++right;
}
}
// reverse1 the subarray
if (min < total) {
reverse1(first, second, a);
// print1 the subarray
print1(a, b);
}
else {
print1(a, b);
}
}
// Driver Code
let n = 4;
let a = [2, 3, 1, 5];
let b = [8, 2, 4, 3];
minimumProdArray(a, b, n);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
1 3 2 5 8 2 4 3 37
Complejidad Temporal: O(N 2 ).
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA