What did i do wrong to get TLE

help
, , , ,
1 
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 linkhttps://www.codechef.com/problems/BUTYPAIR

problem code [BUTYPAIR]

2

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
3

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