Code Detective · Module 6: Reviewing AI answers

Correct isn't enough

Review · 1 of 2

Counting inversions

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

Count the pairs i < j with nums[i] > nums[j], for up to 100,000 numbers. Would you ship this?

Read this lesson as text

Right answers, too slowly. And one number too many.

Counting inversions

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

Count the pairs i < j with nums[i] > nums[j], for up to 100,000 numbers. Would you ship this?

Yes: it's correct and fast enough
No: it's correct but far too slow for 100,000 numbers
No: it gives wrong answers

Show the answer

No: it's correct but far too slow for 100,000 numbers. Every pair is checked: about 5 billion steps. The answer is right, but a time limit makes it wrong in practice. A merge-sort version counts them in about n log n steps.

The last k

n, k = map(int, input().split())
nums = list(map(int, input().split()))
print(sum(nums[n - k - 1:]))

Print the sum of the last k numbers. Would you ship this?

Yes, it's correct
No: it adds one number too many
No: it crashes when k is 1

Show the answer

No: it adds one number too many. The last k numbers start at position n - k, not n - k - 1. Try k = 1 on 1 2 3: it adds 2 + 3. nums[-k:] says it more clearly.