Code Detective · Module 5: Is it fast enough?

Race the clock

Race · 1 of 2

Pairs that cancel out

Solution A

1n = int(input())
2nums = list(map(int, input().split()))
3pairs = 0
4for i in range(n):
5    for j in range(i + 1, n):
6        if nums[i] + nums[j] == 0:
7            pairs += 1
8print(pairs)

Solution B

1n = int(input())
2nums = list(map(int, input().split()))
3seen = {}
4pairs = 0
5for x in nums:
6    pairs += seen.get(-x, 0)
7    seen[x] = seen.get(x, 0) + 1
8print(pairs)

Input: 100,000 numbers between -500 and 499

Both count the pairs that add up to 0. Which finishes within a few seconds?

Read this lesson as text

Two correct solutions. Only one finishes in time.

Pairs that cancel out

Solution A

n = int(input())
nums = list(map(int, input().split()))
pairs = 0
for i in range(n):
    for j in range(i + 1, n):
        if nums[i] + nums[j] == 0:
            pairs += 1
print(pairs)

Solution B

n = int(input())
nums = list(map(int, input().split()))
seen = {}
pairs = 0
for x in nums:
    pairs += seen.get(-x, 0)
    seen[x] = seen.get(x, 0) + 1
print(pairs)

Input: 100,000 numbers between -500 and 499

Both count the pairs that add up to 0. Which finishes within a few seconds?

Only A
Only B
Both

Show the answer

Only B. A tries every pair: about 5 billion checks. B walks once, asking a dictionary how many earlier numbers would cancel the current one. Same answer, a thousand times faster.

First repeat

Solution A

n = int(input())
nums = list(map(int, input().split()))
seen = set()
answer = -1
for x in nums:
    if x in seen:
        answer = x
        break
    seen.add(x)
print(answer)

Solution B

n = int(input())
nums = list(map(int, input().split()))
answer = -1
for j in range(n):
    if nums[j] in nums[:j]:
        answer = nums[j]
        break
print(answer)

Input: 100,000 different numbers (so there's no repeat at all)

Both find the first number that appears twice. Which finishes in time?

Only A
Only B
Both

Show the answer

Only A. B copies and scans nums[:j] for every j: about 5 billion steps when nothing repeats. A keeps a set. The worst case (no repeat) is exactly the test to try.