Dada una array arr[] que consta de N enteros distintos y una array Q[] que representa consultas, la tarea para cada consulta Q[i] es encontrar la suma mínima posible eliminando los elementos de la array de cualquier extremo hasta que se obtenga Q[i] .
Ejemplos:
Entrada: arr[] = {2, 3, 6, 7, 4, 5, 1}, Q[] = {7, 6}
Salida: 17 11
Explicación:
Consulta 1: sacando elementos del final, sum = 1 + 5 + 4 + 7 = 17.
Consulta 2: Elementos emergentes desde el frente, suma = 2 + 3 + 6 = 11.Entrada: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, Q[] = {4, 6, 3}
Salida: 10 21 6
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es atravesar la array dada desde ambos extremos para cada consulta Q[i] e imprimir la suma mínima obtenida de ambos recorridos hasta que se obtiene el elemento con valor Q[i] .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum sum for
// each query after removing elements
// from either ends
void minSum(int arr[], int N, int Q[],
int M)
{
// Traverse the query array
for (int i = 0; i < M; i++) {
int val = Q[i];
int front = 0, rear = 0;
// Traverse the array from
// the front
for (int j = 0; j < N; j++) {
front += arr[j];
// If element equals val,
// then break out of loop
if (arr[j] == val) {
break;
}
}
// Traverse the array from rear
for (int j = N - 1; j >= 0; j--) {
rear += arr[j];
// If element equals val, break
if (arr[j] == val) {
break;
}
}
// Print the minimum of the
// two as the answer
cout << min(front, rear) << " ";
}
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 6, 7, 4, 5, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
int Q[] = { 7, 6 };
int M = sizeof(Q) / sizeof(Q[0]);
// Function Call
minSum(arr, N, Q, M);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find the minimum sum for
// each query after removing elements
// from either ends
static void minSum(int arr[], int N, int Q[],
int M)
{
// Traverse the query array
for (int i = 0; i < M; i++)
{
int val = Q[i];
int front = 0, rear = 0;
// Traverse the array from
// the front
for (int j = 0; j < N; j++)
{
front += arr[j];
// If element equals val,
// then break out of loop
if (arr[j] == val)
{
break;
}
}
// Traverse the array from rear
for (int j = N - 1; j >= 0; j--)
{
rear += arr[j];
// If element equals val, break
if (arr[j] == val)
{
break;
}
}
// Print the minimum of the
// two as the answer
System.out.print(Math.min(front, rear) + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 3, 6, 7, 4, 5, 1 };
int N = arr.length;
int Q[] = { 7, 6 };
int M = Q.length;
// Function Call
minSum(arr, N, Q, M);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach # Function to find the minimum sum for # each query after removing elements # from either ends def minSum(arr, N, Q, M): # Traverse the query array for i in range(M): val = Q[i] front, rear = 0, 0 # Traverse the array from # the front for j in range(N): front += arr[j] # If element equals val, # then break out of loop if (arr[j] == val): break # Traverse the array from rear for j in range(N - 1, -1, -1): rear += arr[j] # If element equals val, break if (arr[j] == val): break # Print the minimum of the # two as the answer print(min(front, rear), end = " ") # Driver Code if __name__ == '__main__': arr = [2, 3, 6, 7, 4, 5, 1] N = len(arr) Q = [7, 6] M = len(Q) # Function Call minSum(arr, N, Q, M) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum sum for
// each query after removing elements
// from either ends
static void minSum(int[] arr, int N, int[] Q,
int M)
{
// Traverse the query array
for(int i = 0; i < M; i++)
{
int val = Q[i];
int front = 0, rear = 0;
// Traverse the array from
// the front
for(int j = 0; j < N; j++)
{
front += arr[j];
// If element equals val,
// then break out of loop
if (arr[j] == val)
{
break;
}
}
// Traverse the array from rear
for(int j = N - 1; j >= 0; j--)
{
rear += arr[j];
// If element equals val, break
if (arr[j] == val)
{
break;
}
}
// Print the minimum of the
// two as the answer
Console.Write(Math.Min(front, rear) + " ");
}
}
// Driver Code
static public void Main()
{
int[] arr = { 2, 3, 6, 7, 4, 5, 1 };
int N = arr.Length;
int[] Q = { 7, 6 };
int M = Q.Length;
// Function Call
minSum(arr, N, Q, M);
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum sum for
// each query after removing elements
// from either ends
function minSum(arr, N, Q, M)
{
// Traverse the query array
for (var i = 0; i < M; i++) {
var val = Q[i];
var front = 0, rear = 0;
// Traverse the array from
// the front
for (var j = 0; j < N; j++) {
front += arr[j];
// If element equals val,
// then break out of loop
if (arr[j] == val) {
break;
}
}
// Traverse the array from rear
for (var j = N - 1; j >= 0; j--) {
rear += arr[j];
// If element equals val, break
if (arr[j] == val) {
break;
}
}
// Print the minimum of the
// two as the answer
document.write( Math.min(front, rear) + " ");
}
}
var arr = [ 2, 3, 6, 7, 4, 5, 1 ];
var N = arr.length;
var Q = [ 7, 6 ];
var M = Q.length;
// Function Call
minSum(arr, N, Q, M);
// This code is contributed by SoumikMondal
</script>
Producción:
17 11
Complejidad temporal: O(N*M)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la técnica Prefix Sum para resolver este problema. Siga los pasos a continuación para resolver el problema:
- Cree dos Mapas auxiliares , digamos M1 y M2 .
- Recorra la array desde el frente e inserte la suma actual calculada hasta cada índice en el Mapa M1 junto con el elemento.
- De manera similar, recorra la array desde atrás e inserte la suma actual calculada hasta cada índice en el mapa M2 junto con el elemento.
- Recorra la array Q[] y para cada elemento Q[i] , imprima el mínimo de M1[Q[i]] y M2[Q[i]] como la suma mínima posible.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum sum
// for each query after removing
// element from either ends till each
// value Q[i]
void minOperations(int arr[], int N,
int Q[], int M)
{
// Stores the prefix sum from
// both the ends of the array
map<int, int> m1, m2;
int front = 0, rear = 0;
// Traverse the array from front
for (int i = 0; i < N; i++) {
front += arr[i];
// Insert it into the map m1
m1.insert({ arr[i], front });
}
// Traverse the array in reverse
for (int i = N - 1; i >= 0; i--) {
rear += arr[i];
// Insert it into the map m2
m2.insert({ arr[i], rear });
}
// Traverse the query array
for (int i = 0; i < M; i++) {
// Print the minimum of the
// two values as the answer
cout << min(m1[Q[i]], m2[Q[i]])
<< " ";
}
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 6, 7, 4, 5, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
int Q[] = { 7, 6 };
int M = sizeof(Q) / sizeof(Q[0]);
// Function Call
minOperations(arr, N, Q, M);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the minimum sum
// for each query after removing
// element from either ends till each
// value Q[i]
static void minOperations(int[] arr, int N,
int[] Q, int M)
{
// Stores the prefix sum from
// both the ends of the array
Map<Integer,
Integer> m1 = new HashMap<Integer,
Integer>();
Map<Integer,
Integer> m2 = new HashMap<Integer,
Integer>();
int front = 0, rear = 0;
// Traverse the array from front
for(int i = 0; i < N; i++)
{
front += arr[i];
// Insert it into the map m1
m1.put(arr[i], front);
}
// Traverse the array in reverse
for(int i = N - 1; i >= 0; i--)
{
rear += arr[i];
// Insert it into the map m2
m2.put(arr[i], rear);
}
// Traverse the query array
for(int i = 0; i < M; i++)
{
// Print the minimum of the
// two values as the answer
System.out.print(Math.min(m1.get(Q[i]),
m2.get(Q[i])) + " ");
}
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 2, 3, 6, 7, 4, 5, 1 };
int N = arr.length;
int[] Q = { 7, 6 };
int M = Q.length;
// Function Call
minOperations(arr, N, Q, M);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach
# Function to find the minimum sum
# for each query after removing
# element from either ends till each
# value Q[i]
def minOperations(arr, N, Q, M):
# Stores the prefix sum from
# both the ends of the array
m1 = {}
m2 = {}
front = 0
rear = 0
# Traverse the array from front
for i in range(N):
front += arr[i]
# Insert it into the map m1
m1[arr[i]] = front
# Traverse the array in reverse
for i in range(N - 1, -1, -1):
rear += arr[i]
# Insert it into the map m2
m2[arr[i]] = rear
# Traverse the query array
for i in range(M):
# Print the minimum of the
# two values as the answer
print(min(m1[Q[i]], m2[Q[i]]),end=" ")
# Driver Code
arr = [2, 3, 6, 7, 4, 5, 1 ]
N = len(arr)
Q = [7,6]
M = len(Q)
# Function Call
minOperations(arr, N, Q, M)
# 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 minimum sum
// for each query after removing
// element from either ends till each
// value Q[i]
static void minOperations(int[] arr, int N,
int[] Q, int M)
{
// Stores the prefix sum from
// both the ends of the array
Dictionary<int,
int> m1 = new Dictionary<int,
int>();
Dictionary<int,
int> m2 = new Dictionary<int,
int>();
int front = 0, rear = 0;
// Traverse the array from front
for(int i = 0; i < N; i++)
{
front += arr[i];
// Insert it into the map m1
m1[arr[i]] = front;
}
// Traverse the array in reverse
for(int i = N - 1; i >= 0; i--)
{
rear += arr[i];
// Insert it into the map m2
m2[arr[i]] = rear;
}
// Traverse the query array
for(int i = 0; i < M; i++)
{
// Print the minimum of the
// two values as the answer
Console.Write(Math.Min(m1[Q[i]],
m2[Q[i]]) + " ");
}
}
// Driver Code
public static void Main()
{
int[] arr = { 2, 3, 6, 7, 4, 5, 1 };
int N = arr.Length;
int[] Q = { 7, 6 };
int M = Q.Length;
// Function Call
minOperations(arr, N, Q, M);
}
}
// This code is contributed by ukasp
Javascript
<script>
// javascript program for the above approach
// Function to find the minimum sum
// for each query after removing
// element from either ends till each
// value Q[i]
function minOperations(arr, N, Q, M)
{
// Stores the prefix sum from
// both the ends of the array
var m1 = new Map();
var m2 = new Map();
var front = 0, rear = 0;
var i;
// Traverse the array from front
for (i = 0; i < N; i++) {
front += arr[i];
// Insert it into the map m1
m1.set(arr[i],front);
}
// Traverse the array in reverse
for (i = N - 1; i >= 0; i--) {
rear += arr[i];
// Insert it into the map m2
m2.set(arr[i], rear);
}
// Traverse the query array
for (i = 0; i < M; i++) {
// Print the minimum of the
// two values as the answer
document.write(Math.min(m1.get(Q[i]), m2.get(Q[i])) + " ");
}
}
// Driver Code
var arr = [2, 3, 6, 7, 4, 5, 1];
var N = arr.length;
var Q = [7, 6];
var M = Q.length;
// Function Call
minOperations(arr, N, Q, M);
// This code is contributed by ipg2016107.
</script>
Producción:
17 11
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA