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.
pairSummingTo(amounts: list<int>, target: int) → list<int>
Go needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
func pairSummingTo(amounts []int, target int) []int {
}Worked examples
| Call | Result |
|---|---|
pairSummingTo([]int{1, 2, 4, 7, 11}, 9) | []int{2, 7} |
pairSummingTo([]int{1, 2, 3, 4}, 5) | []int{1, 4} |
pairSummingTo([]int{1, 2, 3}, 100) | []int{} |
pairSummingTo([]int{}, 3) | []int{} |
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 Go
func pairSummingTo(amounts []int, target int) []int {
i, j := 0, len(amounts)-1
for i < j {
sum := amounts[i] + amounts[j]
if sum == target {
return []int{amounts[i], amounts[j]}
}
if sum < target {
i++
} else {
j--
}
}
return []int{}
}