Pares por debajo de un presupuesto
La misión
Problema
Una tienda lista los precios de sus artículos, y un precio puede incluso ser negativo después de un reembolso. Cuenta los pares de dos artículos distintos cuyos precios suman estrictamente menos que un presupuesto. Dos artículos en posiciones distintas forman un par aparte aunque sus precios sean iguales.
Ejemplos
Input: prices = [4, -2, 0, 3, 1], budget = 3
Output: 5
Por qué: (4, -2), (-2, 0), (-2, 3), (-2, 1) y (0, 1) suman menos de 3
Input: prices = [2, 2, 2], budget = 5
Output: 3
Por qué: cada una de las tres formas de elegir dos de los 2 suma 4
Input: prices = [5], budget = 100
Output: 0
Por qué: caso límite: un solo artículo no puede formar un par
Pistas
0 / 3
Dos bucles anidados revisan cada par y es fácil hacerlos bien. También son cuadráticos, así que una lista diez veces más larga tarda cien veces más.
El orden de los precios no cambia la respuesta, así que puedes ordenarlos primero. En una lista ordenada, si el precio más pequeño y el más grande que quedan caben, ¿qué te dice eso sobre los precios intermedios?
Ordena y luego pon un puntero en cada extremo. Si los dos precios caben en el presupuesto, el precio izquierdo forma par con cada precio hasta el puntero derecho, así que suma esa cantidad y mueve left hacia adentro. Si no, el precio derecho es demasiado grande para cualquiera de los que siguen disponibles, así que mueve right hacia adentro.
- Tiempo objetivo
- O(n log n)
- Espacio objetivo
- O(n)
Restricciones
- prices are integers and can be negative
Solución
Ordenar permite que una sola comparación resuelva muchos pares a la vez. Cuando el precio más pequeño que queda más el precio más grande que queda está por debajo del presupuesto, cada precio entre ellos también cabe con el más pequeño, así que se cuentan todos esos pares y el más pequeño se retira. Cuando la suma es demasiado grande, el precio más grande no cabe con nada de lo que queda y es él el que se retira. Cada paso retira un precio, así que el recorrido después de ordenar es lineal. El tiempo es O(n log n) por el ordenamiento (sorting) y el espacio es O(n) por la copia ordenada.
def pairs_below(prices, budget):
p = sorted(prices)
left, right, count = 0, len(p) - 1, 0
while left < right:
if p[left] + p[right] < budget:
count += right - left # p[left] fits with every price up to right
left += 1
else:
right -= 1 # p[right] fits with nothing left
return count
print(pairs_below([4, -2, 0, 3, 1], 3)) # -> 5
print(pairs_below([2, 2, 2], 5)) # -> 3
print(pairs_below([5], 100)) # -> 0¿Lo que te frena es la idea y no el código? O(n²) y bucles anidados lo explica.