Why I am getting TLE

help
,
1

My issue

for _ in range(int(input())):
n=int(input())
l=list(map(int,input().split()))

d={}

for i in range(n):
    for j in range(i+1,n):
        d[l[i]^l[j]]=d.get(l[i]^l[j],0)+1
        
ans=0
for k,v in d.items():
    ans+=v*(v-1)*4
        
print(ans)

For this code why TLE at test case 9 but where as the same logic in c++ is accepted

My code

# cook your dish here
for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    
    d={}
    
    for i in range(n):
        for j in range(i+1,n):
            d[l[i]^l[j]]=d.get(l[i]^l[j],0)+1
            
    ans=0
    for k,v in d.items():
        ans+=v*(v-1)*4
            
    print(ans)

Problem Link: Xometry (Easy Version) Practice Coding Problem

2

Exactly !

    void Solve(){
        int n;
        cin >> n;
        vector<int> a(n);
        for(int &x: a)
            cin >> x;
        unordered_map<int, int> cnt;
        ll ans = 0;
        for (int i = 0; i < n - 1; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                cnt[a[i] ^ a[j]]++;
            }
        }
        for (auto temp : cnt){
            if(temp.second > 1){
                ans += temp.second * (temp.second - 1)/2;
            }
        }
        cout << 8 * ans << endl;
    }

This does not work for me somehow, however everyone else gets accepted using the similar unordered_map analogy.

1 Like
3

include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here

int t;
cin>>t;

while(t--){
    int n;
    cin>>n;
    
    vector<int> v(n);
    
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    
    long long ans = 0;
    
    unordered_map<int,long long> mp;
    
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            ans+=mp[v[i]^v[j]]++;
        }
    }
    
    cout<<ans*8*1ll<<"\n";
}

}

same thing here

4

Did not work for me as well at the end i use vector instead of unordered_map to got it accepted

5

Please can you share the code to solve using vector.
Thank you.

6

include
#include<bits/stdc++.h>
include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
define ll int128_t
// define int long long
define endl “\n”
define mod 1000000007
using namespace std;

int power(int a, int b) {
int res = 1;

while (b) {
if (b & 1) {
res = res * a % mod;
}

b >>= 1;
a = a * a % mod;

}

return res;
}

int inv(int a) {
return power(a, mod - 2);
}

int32_t main() {
cin.tie(0)->sync_with_stdio(false);
int t;cin>>t;
while(t–){
int n;cin>>n;
int a[n];
for(int i=0;i<n;i++)cin>>a[i];
long long ans=0;
vectormp(2000000,0);
for(int i=0;i<n;i++){
// for(int j=i+1;j<n;j++){
// ans+=mp[a[i]^a[j]];
// }
for(int k=0;k<i;k++){
ans+=mp[a[i]^a[k]];
mp[a[i]^a[k]]++;
}
}

    cout<<ans*8<<endl;
}
cerr << "Time : " << 1000 * ((double)clock()) / CLOCKS_PER_SEC << "ms" << endl;
return 0;

}

1 Like
7

just change map to vector and set all value to 0 it works