Pares abaixo do orçamento
A missão
Problema
Uma loja lista os preços dos itens, e um preço pode até ser negativo depois de um reembolso. Conte os pares de dois itens diferentes cujos preços somam estritamente menos que um orçamento. Dois itens em posições diferentes formam um par à parte, mesmo que os preços sejam iguais.
Exemplos
Input: prices = [4, -2, 0, 3, 1], budget = 3
Output: 5
Por quê: (4, -2), (-2, 0), (-2, 3), (-2, 1) e (0, 1) somam menos de 3
Input: prices = [2, 2, 2], budget = 5
Output: 3
Por quê: cada uma das três formas de escolher dois dos valores 2 soma 4
Input: prices = [5], budget = 100
Output: 0
Por quê: edge case: um item sozinho não forma par
Dicas
0 / 3
Dois loops aninhados verificam cada par e são fáceis de acertar. Mas também são quadráticos: uma lista dez vezes maior leva cem vezes mais tempo.
A ordem dos preços não muda a resposta, então você pode ordená-los primeiro. Em uma lista ordenada, se o menor e o maior preço restantes cabem no orçamento, o que isso diz sobre os preços entre eles?
Ordene e coloque um ponteiro em cada ponta. Se os dois preços ficam abaixo do orçamento, o preço da esquerda forma par com cada preço até o ponteiro da direita, então some essa quantidade e mova o ponteiro da esquerda para dentro. Senão, o preço da direita é grande demais para tudo o que ainda está disponível, então mova o ponteiro da direita para dentro.
- Tempo-alvo
- O(n log n)
- Espaço-alvo
- O(n)
Restrições
- prices are integers and can be negative
Solução
Ordenar permite que uma única comparação resolva muitos pares de uma vez. Quando o menor preço restante mais o maior preço restante fica abaixo do orçamento, todo preço entre eles também cabe junto com o menor, então todos esses pares são contados e o menor sai de cena. Quando a soma é grande demais, o maior preço não cabe com nada do que sobrou, e é ele que sai. Cada passo elimina um preço, então a varredura depois da ordenação é linear. O tempo é O(n log n) pela ordenação, e o espaço é O(n) pela cópia 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)) # -> 0Travou na ideia, e não no código? O(n²) e loops aninhados explica isso.