Dados dos arreglos A[] y B[] de tamaño N cada uno, la tarea es minimizar A[i] + B[j] tal que j ≥ i .
Ejemplos:
Entrada: A[] = {34, 12, 45, 10, 86, 39, 77},
B[] = {5, 42, 29, 63, 30, 33, 20}
Salida: 30
Explicación: Para minimizar la suma , tome i = 3 y j = 6.Entrada: A[] = {34, 17, 45, 10, 19},
B[] = {2, 13, 7, 11, 16}
Salida: 21
Explicación: Para minimizar la suma, tome i y j = 3 .
Enfoque ingenuo: el enfoque ingenuo para resolver este problema es usar 2 bucles for, uno para iterar sobre A[] y otro para iterar sobre B[] . Simplemente verifique y compare todas las posibilidades para minimizar la suma.
A continuación se muestra la implementación del enfoque ingenuo anterior.
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to minimize the sum
int minimumCost(int A[], int B[], int N)
{
int minimuPrice = INT_MAX;
// Checking and comparing for
// all the possibilities
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
int currentPrice = A[i] + B[j];
minimuPrice = min(minimuPrice,
currentPrice);
}
}
// Return the minimum price found
return minimuPrice;
}
// Driver Code
int main()
{
int A[] = { 34, 12, 45, 10, 86, 39, 77 };
int B[] = { 5, 42, 29, 63, 30, 33, 20 };
int N = sizeof(A) / sizeof(A[0]);
// Function Call
cout << minimumCost(A, B, N);
return 0;
}
Java
// Java program for above approach
import java.io.*;
class GFG {
// Function to minimize the sum
public static int minimumCost(int[] A,
int[] B,
int N)
{
int minimuPrice = Integer.MAX_VALUE;
// Checking and comparing
// for all the possibilities
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
int currentPrice
= A[i] + B[j];
minimuPrice
= Math.min(minimuPrice,
currentPrice);
}
}
return minimuPrice;
}
// Driver Code
public static void main(String[] args)
{
int[] A = { 34, 12, 45, 10, 86, 39, 77 };
int[] B = { 5, 42, 29, 63, 30, 33, 20 };
int N = A.length;
System.out.println(minimumCost(A, B, N));
}
}
Python
# Python program for above approach # import the module import sys # Function to minimize the sum def minimumCost(A, B, N): minimuPrice = sys.maxint # Checking and comparing for # all the possibilities for i in range(N): for j in range(i, N): currentPrice = A[i] + B[j] minimuPrice = min(minimuPrice, currentPrice) # Return the minimum price found return minimuPrice; # Driver Code if __name__ == "__main__": A = [ 34, 12, 45, 10, 86, 39, 77 ] B = [ 5, 42, 29, 63, 30, 33, 20 ] N = len(A) # Function Call print(minimumCost(A, B, N)) # This code is contributed by hrithikgarg03188.
C#
// C# program for above approach
using System;
class GFG
{
// Function to minimize the sum
static int minimumCost(int[] A, int[] B, int N)
{
int minimuPrice = Int32.MaxValue;
// Checking and comparing for
// all the possibilities
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
int currentPrice = A[i] + B[j];
minimuPrice
= Math.Min(minimuPrice, currentPrice);
}
}
// Return the minimum price found
return minimuPrice;
}
// Driver Code
public static int Main()
{
int[] A = { 34, 12, 45, 10, 86, 39, 77 };
int[] B = { 5, 42, 29, 63, 30, 33, 20 };
int N = A.Length;
// Function Call
Console.Write(minimumCost(A, B, N));
return 0;
}
}
// This code is contributed by Taranpreet
Javascript
<script>
// JavaScript program for above approach
const INT_MAX = 2147483647;
// Function to minimize the sum
const minimumCost = (A, B, N) => {
let minimuPrice = INT_MAX;
// Checking and comparing for
// all the possibilities
for (let i = 0; i < N; i++) {
for (let j = i; j < N; j++) {
let currentPrice = A[i] + B[j];
minimuPrice = Math.min(minimuPrice,
currentPrice);
}
}
// Return the minimum price found
return minimuPrice;
}
// Driver Code
let A = [34, 12, 45, 10, 86, 39, 77];
let B = [5, 42, 29, 63, 30, 33, 20];
let N = A.length;
// Function Call
document.write(minimumCost(A, B, N));
// This code is contributed by rakeshsahni
</script>
Producción
30
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: una forma eficiente de resolver este problema es crear una array que contenga el valor mínimo hasta el i-ésimo índice desde el extremo posterior de B[] . Luego, recorra A[] y, para cada índice, la suma mínima será la suma del mínimo desde el inicio de A[] y el mínimo desde la parte posterior de B[] hasta ese índice. Siga los pasos a continuación para resolver el problema dado.
- Cree una array para almacenar el valor mínimo desde el extremo posterior de B[] para cada índice.
- Dado que solo hay un valor posible en el último índice, asigne el último valor de índice de la array B[] al último índice de la nueva array.
- Ahora, recorra B[] desde la parte posterior y compare el valor del índice actual (digamos i) en B[] con el índice (i+1) en la nueva array y almacene el valor mínimo de estos dos en el i-ésimo índice del array recién creada.
- Ahora, repita los elementos de X y mire ese índice en la nueva array . Dado que ese índice en la nueva array es el valor más pequeño posible presente en B[] para i y superiores.
A continuación se muestra la implementación del enfoque eficiente anterior.
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate minimum sum
int minimumCost(int A[], int B[], int N)
{
// For storing the minimum value
// from rear end of B[]
int cheapestPossible[N];
// Only one possible value on last index
cheapestPossible[N - 1] = B[N - 1];
for (int i = (N - 2); i >= 0; i--) {
// The lowest possible sum at
// index i and above
cheapestPossible[i]
= min(cheapestPossible[i + 1],
B[i]);
}
// For storing minimum sum
int minimumPrice = INT_MAX;
// Adding the current value of A[] and
// minimum value of B[] after i and
// comparing it with the last minimum sum
for (int i = 0; i < N; i++) {
minimumPrice
= min(minimumPrice,
A[i] + cheapestPossible[i]);
}
return minimumPrice;
}
// Driver Code
int main()
{
int A[] = { 34, 12, 45, 10, 86, 39, 77 };
int B[] = { 5, 42, 29, 63, 30, 33, 20 };
int N = sizeof(A) / sizeof(A[0]);
// Function Call
cout << minimumCost(A, B, N);
return 0;
}
Java
// Java program for above approach
import java.io.*;
class GFG {
// Function to calculate minimum sum
public static int minimumCost(int[] A,
int[] B,
int N)
{
// For storing the minimum value
// from rear end of B[]
int[] cheapestPossible = new int[N];
// Only one possible value
// on last index
cheapestPossible[N - 1]
= B[N - 1];
for (int i = (N - 2); i >= 0; i--) {
// The lowest possible sum at
// index i and above
cheapestPossible[i]
= Math.min(cheapestPossible[i + 1],
B[i]);
}
// For storing minimum sum
int minimumPrice = Integer.MAX_VALUE;
// Adding the current value of A[]
// and minimum value of B[] after i
// and comparing it with
// the last minimum sum obtained
for (int i = 0; i < N; i++) {
minimumPrice = Math.min(
minimumPrice, A[i]
+ cheapestPossible[i]);
}
return minimumPrice;
}
// Driver code
public static void main(String[] args)
{
int[] A = { 34, 12, 45, 10, 86, 39, 77 };
int[] B = { 5, 42, 29, 63, 30, 33, 20 };
int N = A.length;
System.out.println(minimumCost(A, B, N));
}
}
Python3
# Python 3 program for above approach import sys # Function to calculate minimum sum def minimumCost(A, B, N): # For storing the minimum value # from rear end of B[] cheapestPossible = [0]*N # Only one possible value on last index cheapestPossible[N - 1] = B[N - 1] for i in range(N - 2 ,- 1, -1): # The lowest possible sum at # index i and above cheapestPossible[i] = min(cheapestPossible[i + 1], B[i]) # For storing minimum sum minimumPrice = sys.maxsize # Adding the current value of A[] and # minimum value of B[] after i and # comparing it with the last minimum sum for i in range(N): minimumPrice = min(minimumPrice, A[i] + cheapestPossible[i]) return minimumPrice # Driver Code if __name__ == "__main__": A = [34, 12, 45, 10, 86, 39, 77] B = [5, 42, 29, 63, 30, 33, 20] N = len(A) # Function Call print(minimumCost(A, B, N)) # This code is contributed by ukasp.
C#
// C# program for above approach
using System;
using System.Collections.Generic;
public class GFG {
// Function to calculate minimum sum
public static int minimumCost(int[] A,
int[] B,
int N)
{
// For storing the minimum value
// from rear end of []B
int[] cheapestPossible = new int[N];
// Only one possible value
// on last index
cheapestPossible[N - 1]
= B[N - 1];
for (int i = (N - 2); i >= 0; i--) {
// The lowest possible sum at
// index i and above
cheapestPossible[i]
= Math.Min(cheapestPossible[i + 1],
B[i]);
}
// For storing minimum sum
int minimumPrice = int.MaxValue;
// Adding the current value of []A
// and minimum value of []B after i
// and comparing it with
// the last minimum sum obtained
for (int i = 0; i < N; i++) {
minimumPrice = Math.Min(
minimumPrice, A[i]
+ cheapestPossible[i]);
}
return minimumPrice;
}
// Driver code
public static void Main(String[] args)
{
int[] A = { 34, 12, 45, 10, 86, 39, 77 };
int[] B = { 5, 42, 29, 63, 30, 33, 20 };
int N = A.Length;
Console.WriteLine(minimumCost(A, B, N));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// javascript program for above approach
// Function to calculate minimum sum
function minimumCost(A, B, N)
{
// For storing the minimum value
// from rear end of B
var cheapestPossible = Array.from({length: N}, (_, i) => 0);
// Only one possible value
// on last index
cheapestPossible[N - 1]
= B[N - 1];
for (var i = (N - 2); i >= 0; i--) {
// The lowest possible sum at
// index i and above
cheapestPossible[i]
= Math.min(cheapestPossible[i + 1],
B[i]);
}
// For storing minimum sum
var minimumPrice = Number.MAX_VALUE;
// Adding the current value of A
// and minimum value of B after i
// and comparing it with
// the last minimum sum obtained
for (var i = 0; i < N; i++) {
minimumPrice = Math.min(
minimumPrice, A[i]
+ cheapestPossible[i]);
}
return minimumPrice;
}
// Driver code
var A = [ 34, 12, 45, 10, 86, 39, 77 ];
var B = [ 5, 42, 29, 63, 30, 33, 20 ];
var N = A.length;
document.write(minimumCost(A, B, N));
// This code is contributed by shikhasingrajput
</script>
Producción
30
Complejidad temporal: O(N)
Espacio auxiliar: O(N)