Saltar al contenido

Pares por debajo de un presupuesto

Fácil#sorting#two-pointers~20 min

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

Tiempo objetivo
O(n log n)
Espacio objetivo
O(n)

Restricciones

  • prices are integers and can be negative

¿Lo que te frena es la idea y no el código? O(n²) y bucles anidados lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio