- What is the expected time complexity for this question?
- If less then O(n^2), someone please explain their approach… or
just hint like what is to be used?
I just can’t do better than O(n^2).
from collections import defaultdict as dd n = int(input()) a = list(map(int,input().split())) rights = dd(lambda:0) lefts = [a] for i in range(1,n): rights[a[i]] += 1 ans = 0 for i in range(1,n): ele = a[i] rights[ele] -= 1 for left in lefts: if rights[2*ele-left] >= 1: ans += rights[2*ele-left] lefts.append(ele) print(ans)
Problem Link: COUNTARI Problem - CodeChef