ChaituBoi's blog

By ChaituBoi, 4 weeks ago, In English

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;

}

 
 
 
 
  • Vote: I like it
  • -23
  • Vote: I do not like it

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Try with a vector of long long.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      nums[i]*(nums[i]-1) overflows the int limit when nums[i]=10^5.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Thank you for solving my tasks!