# What did i do wrong to get TLE

``````try:
test=int(input())
result =list()
while test!=0:
n= int(input())
numbers=list(map(int,input().split()))
set1=set(numbers)
sum1=0
for i in set1:
j=numbers.count(i)
pairs=(n-j)*j
sum1+=pairs
result.append(sum1)

test-=1
for item in result:
print(item)
except :
pass
``````

problem code [BUTYPAIR]

For every number, you are finding it’s count by iterating through the array which makes it O(n^2). You can do this in a single iteration i.e in O(n) by using a dictionary in Python or map in C++

``````d = {}
for i in numbers:
d[i] = d.get(i, 0) + 1

for i in d:
pairs = (n-d[i])*d[i]
sum1 += pairs
``````
1 Like

you can try this code,it will give right ans.
the only thing you have to do discard those i and j such that ai == aj.
if total such numbers are x then only u need to subtract x*(x-1) from ans.
#include<bits/stdc++.h>
#pragma GCC optimise(“Ofast”)
#pragma GCC target(“avx”,“avx2”,“fma”)
using namespace std;
#define int long long

``````signed main() {

ios_base ::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--){
int N;
cin >> N;
unordered_map<int,int> Map;
int* arr = new int[N];
for(int i = 0 ; i < N ; i++){
cin >> arr[i];
Map[arr[i]]++;
}
int Ans = N*(N-1);
for(auto x : Map){
if(x.second > 1)
Ans -= x.second*(x.second-1);
}
cout<<Ans<<"\n";
}
return 0;
}``````
1 Like