Dada una array ordenada arr[] y un conjunto Q que tiene M consultas, donde cada consulta tiene valores X e Y , la tarea es encontrar la suma de todos los números enteros menores que X y mayores que Y presentes en la array.
Nota: X e Y pueden o no estar presentes en la array.
Ejemplos:
Entrada: arr[] = [3 5 8 12 15], Q = {{5, 12}, {4, 8}}
Salida:
18
30
Explicación:
Para la consulta 1, X = 5 e Y = 12. Suma = 3 ( < 5) + 15( > 12) = 18.
Para la consulta 2, X = 4 e Y = 8. Suma = 3( < 4) + 15 ( > 8) + 12 ( > 8) = 30.Entrada: arr[] = [4 7 7 12 15], Q = {{3, 8}, {4, 8}}
Salida:
27
27
Explicación:
Para la consulta 1, X = 3 e Y = 8. Suma = 12 ( > 8) + 15 ( > 8) = 27.
Para la consulta 2, Suma = 12 + 15 = 27.
Acercarse:
- Cree una array de suma de prefijos donde prefix_sum[i] denota la suma de arr[0] + arr[1] + … arr[i] .
- Encuentre el último índice i que tiene un valor menor que X y extraiga la suma del prefijo hasta el i -ésimo índice. El índice se puede obtener en complejidad O(logN) usando bisect_left() o lower_bound() en Python y C++ respectivamente.
- De manera similar, encuentre el primer índice i en la array con un valor mayor que Y y calcule la suma prefix_sum[n-1] – prefix_sum[i-1] . Las funciones incorporadas bisect () y upper_bound() en Python y C++ respectivamente, realizan la operación requerida en O(logN) .
- La suma de los dos resultados calculados en los dos pasos anteriores es la respuesta requerida. Siga repitiendo estos pasos para cada consulta.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python code for the above program
from bisect import bisect, bisect_left
def createPrefixSum(ar, n):
# Initialize prefix sum
# array
prefix_sum = [0]*n
# Initialize prefix_sum[0]
# by ar[0]
prefix_sum[0] = ar[0]
# Compute prefix sum for
# all indices
for i in range(1, n):
prefix_sum[i] = prefix_sum[i-1]+ar[i]
return prefix_sum
# Function to return sum of all
# elements less than X
def sumLessThanX(ar, x, prefix_xum):
# Index of the last element
# which is less than x
pos_x = bisect_left(ar, x) - 1
if pos_x >= 0 :
return prefix_sum[pos_x]
# If no element is less than x
else:
return 0
# Function to return sum of all
# elements greater than Y
def sumGreaterThanY(ar, y, prefix_sum):
# Index of the first element
# which is greater than y
pos_y = bisect(ar, y)
pos_y -= 1
if pos_y < len(ar)-1 :
return prefix_sum[-1]-prefix_sum[pos_y]
# If no element is greater than y
else:
return 0
def solve(ar, x, y, prefix_sum):
ltx = sumLessThanX(ar, x, prefix_sum)
gty = sumGreaterThanY(ar, y, prefix_sum)
# printing the final sum
print(ltx + gty)
def print_l(lb, ub):
print("sum of integers less than {}".format(lb)
+ " and greater than {} is ".format(ub),
end = '')
if __name__ == '__main__':
# example 1
ar = [3, 6, 6, 12, 15]
n = len(ar)
prefix_sum = createPrefixSum(ar, n)
# for query 1
q1x = 5
q1y = 12
print_l(q1x, q1y)
solve(ar, q1x, q1y, prefix_sum)
# for query 2
q2x = 7
q2y = 8
print_l(q2x, q2y)
solve(ar, q2x, q2y, prefix_sum)
sum of integers less than 5 and greater than 12 is 18 sum of integers less than 7 and greater than 8 is 42
Complejidad de tiempo: O(N + (M * logN))
Complejidad de espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por imankalyan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA