SEDMAX lunchtime

general
,
1

I wrote a code for february lunchtime 2021, question SEDMAX.
I’m getting correct answers for the input examples but when i submit i get wrong answers and tle. Can someone please check the code…

    T = int(input())
    for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    lst = []
    A.sort(reverse = True)
    for i in range(N):
        for j in range(i+1,N):
            c = A[i]-A[j]
            lst.append(c)
    cost = set(lst)
    size = len(cost)
    print(size)
2

That’s an O(N^2) solution. You might want to optimise it in terms of time complexity.

1 Like
3

time limit exceeded because your solution is of O(n^2) and n can be upto 10^5(it take 10^10 steps and you are only allowed 10^8(1 sec) in given question)
O(n^2)-when you are using 2 nested for loops-> (n-1)+(n-2)+…+2+1=n*(n-1)/2=n^2

1 Like
4

So what i wanted to do by those for loops was let suppose i have a list, l = [13,10,8,5]
then create pairs (13,10), (13,8), (13,5), (10,8), (10,5), (8,5). Is there any better way to do that