Consultas para encontrar la suma mínima de elementos de array desde cualquier extremo de una array

Dada una array arr[] que consta de N enteros distintos y una array consultas[] que consta de Q consultas, la tarea para cada consulta es encontrar consultas[i] en la array y calcular la suma mínima de los elementos de la array desde el principio y final de la array hasta queries[i] .

Ejemplos:

Entrada: arr[] = {2, 3, 6, 7, 4, 5, 30}, Q = 2, queries[] = {6, 5}
Salida: 11 27
Explicación:
Consulta 1: Suma desde el inicio = 2 + 3 + 6 = 11. Suma desde el final = 30 + 5 + 4 + 7 + 6 = 52. Por lo tanto, 11 es la respuesta requerida.
Consulta 2: Suma desde el inicio = 27. Suma desde el final = 35. Por lo tanto, 27 es la respuesta requerida.

Entrada: arr[] = {1, 2, -3, 4}, Q = 2, consultas[] = {4, 2}
Salida: 4 2

Enfoque ingenuo: el enfoque más simple es recorrer la array hasta las consultas [i] para cada consulta y calcular la suma desde el final y desde el inicio de la array. Finalmente, imprime el mínimo de las sumas obtenidas.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation
// of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the minimum
// sum from either end of the arrays
// for the given queries
void calculateQuery(int arr[], int N,
                    int query[], int M)
{
    // Traverse the query[] array
    for (int i = 0; i < M; i++) {
        int X = query[i];
 
        // Stores sum from start
        // and end of the array
        int sum_start = 0, sum_end = 0;
 
        // Calculate distance from start
        for (int j = 0; j < N; j++) {
 
            sum_start += arr[j];
            if (arr[j] == X)
                break;
        }
 
        // Calculate distance from end
        for (int j = N - 1; j >= 0; j--) {
 
            sum_end += arr[j];
            if (arr[j] == X)
                break;
        }
 
        cout << min(sum_end, sum_start) << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 3, 6, 7, 4, 5, 30 };
    int queries[] = { 6, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int M = sizeof(queries)
            / sizeof(queries[0]);
 
    calculateQuery(arr, N, queries, M);
 
    return 0;
}

// Java implementation of the
// above approach
import java.util.*;
import java.lang.*;
 
public class GFG
{
 
  // Function to calculate the minimum
  // sum from either end of the arrays
  // for the given queries
  static void calculateQuery(int arr[], int N,
                             int query[], int M)
  {
 
    // Traverse the query[] array
    for (int i = 0; i < M; i++)
    {
      int X = query[i];
 
      // Stores sum from start
      // and end of the array
      int sum_start = 0, sum_end = 0;
 
      // Calculate distance from start
      for (int j = 0; j < N; j++)
      {
        sum_start += arr[j];
        if (arr[j] == X)
          break;
      }
 
      // Calculate distance from end
      for (int j = N - 1; j >= 0; j--)
      {
        sum_end += arr[j];
        if (arr[j] == X)
          break;
      }
      System.out.print(Math.min(sum_end, sum_start) + " ");
    }
  }
 
  // Driver Code
  public static void main (String[] args)
  {
    int arr[] = { 2, 3, 6, 7, 4, 5, 30 };
    int queries[] = { 6, 5 };
    int N = arr.length;
    int M = queries.length;
    calculateQuery(arr, N, queries, M);
  }
}
 
// This code is contributed by jana_sayantan.

# Python 3 implementation
# of the above approach
 
# Function to calculate the minimum
# sum from either end of the arrays
# for the given queries
 
 
def calculateQuery(arr, N, query, M):
 
    # Traverse the query[] array
    for i in range(M):
        X = query[i]
 
        # Stores sum from start
        # and end of the array
        sum_start = 0
        sum_end = 0
 
        # Calculate distance from start
        for j in range(N):
 
            sum_start += arr[j]
            if (arr[j] == X):
                break
 
        # Calculate distance from end
        for j in range(N - 1, -1, -1):
 
            sum_end += arr[j]
            if (arr[j] == X):
                break
        print(min(sum_end, sum_start), end=" ")
 
# Driver Code
if __name__ == "__main__":
 
    arr = [2, 3, 6, 7, 4, 5, 30]
    queries = [6, 5]
    N = len(arr)
    M = len(queries)
 
    calculateQuery(arr, N, queries, M)
 
    # This code is contributed by chitranayal.

// C# implementation
// of the above approach
using System;
class GFG {
 
  // Function to calculate the minimum
  // sum from either end of the arrays
  // for the given queries
  static void calculateQuery(int[] arr, int N,
                             int[] query, int M)
  {
     
    // Traverse the query[] array
    for (int i = 0; i < M; i++) {
      int X = query[i];
 
      // Stores sum from start
      // and end of the array
      int sum_start = 0, sum_end = 0;
 
      // Calculate distance from start
      for (int j = 0; j < N; j++) {
 
        sum_start += arr[j];
        if (arr[j] == X)
          break;
      }
 
      // Calculate distance from end
      for (int j = N - 1; j >= 0; j--) {
 
        sum_end += arr[j];
        if (arr[j] == X)
          break;
      }
 
      Console.Write(Math.Min(sum_end, sum_start) + " ");
    }
  }
 
  // Driver code
  static void Main()
  {
    int[] arr = { 2, 3, 6, 7, 4, 5, 30 };
    int[] queries = { 6, 5 };
    int N = arr.Length;
    int M = queries.Length;
 
    calculateQuery(arr, N, queries, M);
  }
}
 
// This code is contributed by divyesh072019.

<script>
 
// Javascript implementation of the above approach
 
// Function to calculate the minimum
// sum from either end of the arrays
// for the given queries
function calculateQuery(arr, N, query, M)
{
     
    // Traverse the query[] array
    for(let i = 0; i < M; i++)
    {
        let X = query[i];
         
        // Stores sum from start
        // and end of the array
        let sum_start = 0, sum_end = 0;
         
        // Calculate distance from start
        for(let j = 0; j < N; j++)
        {
            sum_start += arr[j];
             
            if (arr[j] == X)
                break;
        }
         
        // Calculate distance from end
        for(let j = N - 1; j >= 0; j--)
        {
            sum_end += arr[j];
             
            if (arr[j] == X)
                break;
        }
        document.write(Math.min(
            sum_end, sum_start) + " ");
    }
}
 
// Driver code
let arr = [ 2, 3, 6, 7, 4, 5, 30 ];
let queries = [ 6, 5 ];
let N = arr.length;
let M = queries.length;
 
calculateQuery(arr, N, queries, M);
 
// This code is contributed by suresh07
 
</script>

11 27

Complejidad temporal: O(Q * N)
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de espacio adicional y el concepto de suma de prefijos y suma de sufijos y para responder a cada consulta en una complejidad computacional constante. La idea es preprocesar sumas de prefijos y sufijos para cada índice. Siga los pasos a continuación para resolver el problema:

• Inicialice dos variables, digamos prefijo y sufijo .
• Inicialice un mapa desordenado , digamos mp, para mapear elementos de array como claves para pares en los que el primer valor da el prefijo sum y el segundo valor da el sufijo sum.
• Recorra la array y siga agregando arr[i] al prefijo y guárdelo en el mapa con arr[i] como clave y prefijo como valor.
• Recorra la array a la inversa y siga agregando arr[i] al sufijo y almacene en el mapa con arr[i] como clave y sufijo como valor.
• Ahora recorra la array consultas[] y para cada consulta consultas[i] , imprima el valor del mínimo de mp[consultas[i]].primero y mp[consultas[i]].segundo como resultado.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation
// of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum sum
// for the given queries
void calculateQuery(int arr[], int N,
                    int query[], int M)
{
 
    // Stores prefix and suffix sums
    int prefix = 0, suffix = 0;
 
    // Stores pairs of prefix and suffix sums
    unordered_map<int, pair<int, int> > mp;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // Add element to prefix
        prefix += arr[i];
 
        // Store prefix for each element
        mp[arr[i]].first = prefix;
    }
 
    // Traverse the array in reverse
    for (int i = N - 1; i >= 0; i--) {
 
        // Add element to suffix
        suffix += arr[i];
 
        // Storing suffix for each element
        mp[arr[i]].second = suffix;
    }
 
    // Traverse the array queries[]
    for (int i = 0; i < M; i++) {
 
        int X = query[i];
 
        // Minimum of suffix
        // and prefix sums
        cout << min(mp[X].first,
                    mp[X].second)
             << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 3, 6, 7, 4, 5, 30 };
    int queries[] = { 6, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int M = sizeof(queries) / sizeof(queries[0]);
 
    calculateQuery(arr, N, queries, M);
 
    return 0;
}

// Java implementation
// of the above approach
import java.util.*;
 
class GFG
{
  static class pair<E,P>
  {
    E first;
    P second;
    public pair(E first, P second) 
    {
      this.first = first;
      this.second = second;
    }   
  }
 
  // Function to find the minimum sum
  // for the given queries
  @SuppressWarnings({ "unchecked", "rawtypes" })
  static void calculateQuery(int arr[], int N,
                             int query[], int M)
  {
 
    // Stores prefix and suffix sums
    int prefix = 0, suffix = 0;
 
    // Stores pairs of prefix and suffix sums
    HashMap<Integer, pair > mp = new HashMap<>();
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
      // Add element to prefix
      prefix += arr[i];
 
      // Store prefix for each element
      mp.put(arr[i], new pair(prefix,0));
    }
 
    // Traverse the array in reverse
    for (int i = N - 1; i >= 0; i--) {
 
      // Add element to suffix
      suffix += arr[i];
 
      // Storing suffix for each element
      mp.put(arr[i], new pair(mp.get(arr[i]).first,suffix));
    }
 
    // Traverse the array queries[]
    for (int i = 0; i < M; i++) {
 
      int X = query[i];
 
      // Minimum of suffix
      // and prefix sums
      System.out.print(Math.min((int)mp.get(X).first,
                                (int)mp.get(X).second)
                       + " ");
    }
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int arr[] = { 2, 3, 6, 7, 4, 5, 30 };
    int queries[] = { 6, 5 };
    int N = arr.length;
    int M = queries.length;
 
    calculateQuery(arr, N, queries, M);
 
  }
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation
# of the above approach
 
# Function to find the minimum sum
# for the given queries
def calculateQuery(arr, N, query, M):
     
    # Stores prefix and suffix sums
    prefix = 0
    suffix = 0
     
    # Stores pairs of prefix and suffix sums
    mp = {}
     
    # Traverse the array
    for i in range(N):
         
        # Add element to prefix
        prefix += arr[i]
         
        # Store prefix for each element
        mp[arr[i]] = [prefix, 0]
     
    # Traverse the array in reverse
    for i in range(N - 1, -1, -1):
         
        # Add element to suffix
        suffix += arr[i]
         
        # Storing suffix for each element
        mp[arr[i]] = [mp[arr[i]][0], suffix]
     
    # Traverse the array queries[]
    for i in range(M):
        X = query[i]
         
        # Minimum of suffix
        # and prefix sums
        print(min(mp[X][0], mp[X][1]), end = " ")
 
# Driver Code
arr = [ 2, 3, 6, 7, 4, 5, 30 ]
queries = [ 6, 5 ]
N = len(arr)
M = len(queries)
 
calculateQuery(arr, N, queries, M)
 
# This code is contributed by avanitrachhadiya2155

// C# implementation
// of the above approach
using System;
using System.Collections.Generic;
class GFG {
 
  // Function to find the minimum sum
  // for the given queries
  static void calculateQuery(int[] arr, int N,
                             int[] query, int M)
  {
 
    // Stores prefix and suffix sums
    int prefix = 0, suffix = 0;
 
    // Stores pairs of prefix and suffix sums
    Dictionary<int, Tuple<int,int>> mp =
      new Dictionary<int, Tuple<int,int>>();
 
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
 
      // Add element to prefix
      prefix += arr[i];
 
      // Store prefix for each element
      mp[arr[i]] = new Tuple<int,int>(prefix, 0);
    }
 
    // Traverse the array in reverse
    for (int i = N - 1; i >= 0; i--)
    {
 
      // Add element to suffix
      suffix += arr[i];
 
      // Storing suffix for each element
      mp[arr[i]] = new Tuple<int,int>(mp[arr[i]].Item1, suffix);
    }
 
    // Traverse the array queries[]
    for (int i = 0; i < M; i++)
    {
      int X = query[i];
 
      // Minimum of suffix
      // and prefix sums
      Console.Write(Math.Min(mp[X].Item1, mp[X].Item2) + " ");
    }
  }
 
  // Driver code
  static void Main() {
    int[] arr = { 2, 3, 6, 7, 4, 5, 30 };
    int[] queries = { 6, 5 };
    int N = arr.Length;
    int M = queries.Length;
 
    calculateQuery(arr, N, queries, M);
  }
}
 
// This code is contributed by divyeshrabadiya07.

<script>
 
// Javascript implementation
// of the above approach
 
// Function to find the minimum sum
// for the given queries
function calculateQuery(arr, N, query, M)
{
 
    // Stores prefix and suffix sums
    var prefix = 0, suffix = 0;
 
    // Stores pairs of prefix and suffix sums
    var mp = new Map();
 
    // Traverse the array
    for(var i = 0; i < N; i++)
    {
         
        // Add element to prefix
        prefix += arr[i];
 
        // Store prefix for each element
        if (!mp.has(arr[i]))
        {
            mp.set(arr[i], [0, 0]);
        }
        var tmp = mp.get(arr[i]);
        tmp[0] = prefix;
        mp.set(arr[i], tmp);
    }
 
    // Traverse the array in reverse
    for(var i = N - 1; i >= 0; i--)
    {
         
        // Add element to suffix
        suffix += arr[i];
 
        // Storing suffix for each element
        if (!mp.has(arr[i]))
        {
            mp.set(arr[i], [0, 0]);
        }
        var tmp = mp.get(arr[i]);
        tmp[1] = suffix;
        mp.set(arr[i], tmp);
    }
 
    // Traverse the array queries[]
    for(var i = 0; i < M; i++)
    {
        var X = query[i];
 
        var tmp = mp.get(X);
         
        // Minimum of suffix
        // and prefix sums
        document.write(Math.min(tmp[0], tmp[1]) + " ");
    }
}
 
// Driver Code
var arr = [ 2, 3, 6, 7, 4, 5, 30 ];
var queries = [ 6, 5 ];
var N = arr.length;
var M = queries.length;
 
calculateQuery(arr, N, queries, M);
 
// This code is contributed by rutvik_56
 
</script>

11 27

Complejidad temporal: O(M + N)
Espacio auxiliar: O(N)