Editorial for Markers Tower

Editorial

Since we want to find 2 markers with a total height of k, this problem is similar to the classic 2 sum problem you may have seen elsewhere. Instead of finding whether there exist two heights that sums to k, you would have to count the number of pairs of marker height, without overcounting cases where its the same two markers at different order.

This is simply achieved by having first marker index i iterate from 0 to n-1, and for each i have second index j iterate from i + 1 to n. A common strategy to cover all combinations of 2 elements (and more), with a time complexity of O(n^2) that is sufficient for the problem. (Challenge: can you solve the problem with faster worst case/average case time complexity?)

Sample solution:

n, k = map(int, input().split())
arr = list(map(int, input().split()))
res = 0

for i in range(n):
    for j in range(i + 1, n):
        if arr[i] + arr[j] == k:
            res += 1

print(res)