The two readings that add up
A reconciliation tool has a sorted column of amounts and a difference to explain. It looks for the two amounts that together account for it.
- The amounts arrive sorted ascending.
- Return the two amounts, smaller first.
- If several pairs work, return the one with the smallest first amount.
- If no pair adds up, return an empty list.
- An amount cannot pair with itself — the two have to be at different positions.
pair_summing_to(amounts: list<int>, target: int) → list<int>
Where you start
def pair_summing_to(amounts: list[int], target: int) -> list[int]:
Worked examples
| Call | Result |
|---|---|
pair_summing_to([1, 2, 4, 7, 11], 9) | [2, 7] |
pair_summing_to([1, 2, 3, 4], 5) | [1, 4] |
pair_summing_to([1, 2, 3], 100) | [] |
pair_summing_to([], 3) | [] |
Hint
Sorted input means you can start at both ends. If the two ends add up to too much, the right end is too big; if too little, the left end is too small.
Reference solution in Python
def pair_summing_to(amounts: list[int], target: int) -> list[int]:
i, j = 0, len(amounts) - 1
while i < j:
total = amounts[i] + amounts[j]
if total == target:
return [amounts[i], amounts[j]]
if total < target:
i += 1
else:
j -= 1
return []