### ChaituBoi's blog

By ChaituBoi, 4 months ago,

Now what i did was similar to editorial. The problem isnt with the approach but with the fact that if use operation ans+=(n*(n-1))/2 i get wrong answer due to integer overflow, now I AM using long long but still it gives -ve answer in 2nd test case which is ofcourse due to overflow. To solve this what i did was first divide n or (n-1) by 2 (depending upon parity) and then multiplying and got answer accepted. Can someone tell why this is happening?? I know i would probably be a very dumb mistake but plz dont judge harshly. :D

MY CODE:

#include<bits/stdc++.h>

using namespace std;

//void swap(int &a,int &b){

// int tmp=a;a=b;b=tmp;

//}

int size(long long a){

int n=0;

while(a!=0){

n++;

a/=2;

}

return n;

}

int main(){

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int t,n;

cin>>t;

while(t--){

cin>>n;

long long A[n],ans=0;

for(int i=0;i<n;i++)cin>>A[i];



vector<int>nums(32,0);

for(int i=0;i<n;i++){

nums[size(A[i])]++;

}

for(int i=0;i<32;i++){

// long long a=nums[i],b=nums[i]-1;

// if(nums[i]%2==0){

// a/=2;

// }

// else{

// b/=2;

// }

// ans+=(a*b);

ans+=((nums[i]*(nums[i]-1))/2);

}

cout<<ans<<"\n";

}



return 0;

}

• -23

 » 4 months ago, # | ← Rev. 3 →   0 Try with a vector of long long.
•  » » 4 months ago, # ^ |   0 That worked, but i am curious that vector should be sufficient since there are only 10^5 elements in total and i am using the vector to store number of occurences (with size i) which obviously can't be more than 10^5 for any test case!
•  » » » 4 months ago, # ^ |   0 nums[i]*(nums[i]-1) overflows the int limit when nums[i]=10^5.
•  » » » » 4 months ago, # ^ |   0 whether the answer overflows or not, doesn't it depend on the size of containor which is long long , in this case. Or it does on the operands too?
•  » » » » » 4 months ago, # ^ |   0 nums[i] is an int, so multiplying two of them yields an int, which overflows. The value (which has overflowed) is stored as a long long, but since it overflowed the answer is wrong.
 » 4 months ago, # |   +9 Thank you for solving my tasks!
•  » » 4 months ago, # ^ |   +8 learned a lot, so thank YOU