Official

E - Uniqueness Editorial by en_translator


The following code processes each person to check if the other persons have the same number. However, the time complexity of this implementation is \(\Theta(N^2)\), which leads to TLE (Time Limit Exceeded). Note that even if your code does not seem to have a double loop, if you use functions or methods like filter or all, your code will still have the same computational complexity.

for i in 1..N:
  ok = true
  for j in 1..N:
    if i != j and A[i] == A[j]:
      ok = false
  if ok:
    ...

Consider the following associative array:
\(\mathrm{dict}[v]=The indices of persons who have integer v \)
This associative array can be constructed in \(O(N\log N)\) time. In this associative array, the size of set is \(1\) if and only if the other persons do not have the same integer. Therefore, by scanning the contents of the associative array, the answer can be found in a total of \(O(N\log N)\) time.

Sample code (Python)

from collections import defaultdict

N=int(input())
A=list(map(int,input().split()))

d=defaultdict(list)
for i,a in enumerate(A):
  d[a].append(i)

for key in sorted(d, reverse=True):
  if len(d[key])==1:
    print(d[key][0]+1)
    exit()

print(-1)

posted:
last update: