The problem
A goods yard has a list a of wagon loads. Return True if two loads at different positions add up to exactly target, and False otherwise.
has_pair_sum([40, 25, 60, 15], 75)
# True: 60 + 15
has_pair_sum([40, 25, 60, 15], 50)
# False: there is only one 25
has_pair_sum([5, 3, 5], 10)
# True: two different 5s
Checking every pair is correct, but it takes about n × n steps: Θ(n²). Read the limits and work out, as in lesson 3, whether that is fast enough.
Limits
- Up to 100,000 loads. Loads and the target are whole numbers, and may be negative.
Builds on BIGO-3 Growth rates and BIGO-4 Space cost.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
8 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | A pair exists | Not run | |
| 2 | No pair | Not run | |
| 3 | The same value twice | Not run | |
| 4 | One value cannot pair with itself | Not run | |
| 5 | Empty and single | Not run | |
| 6 | Negative values | Not run | |
| 7 | 100,000 values, no pair | Not run | |
| 8 | 100,000 values, pair at the end | Not run |