Sum of two numbers in array

[1vf9z8AR]

Question-
https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/practice-problems/algorithm/cricket-balls/

Issue-
Code passes for test cases but for other test cases which are really huge it does not pass

My logic-
Store frequency of each number and use that to compute answer.

  #include<iostream>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t>0)
    {
        int freq[100000];
        for(int i=1;i<100000;i++)
            freq[i]=0;
        freq[0]=1;
        int n,k;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            int temp;
            cin>>temp;
            freq[temp]++;
        }
        cin>>k;
        long long int ans=0;
        for(int i=0;i<=k/2;i++)
        {
            if(k-i==i)
            {
                int start=freq[i]-1;
                while(start>0)
                {
                    ans+=start;
                    start--;
                }
            }
            else
                ans+=freq[k-i]*freq[i];
        }
        cout<<ans<<endl;
        t--;
    }
    return 0;
}

[ne555]

> freq[0]=1;
¿why are you doing that?
the problem specifically says that there are no empty boxes


also, if you have TLE, you may replace lines 27--32 with (freq[i]*(freq[i]+1)) / 2

[1vf9z8AR]

@ne555

I am not getting tle. Execution time is in milliseconds.

I am doing freq[0]=1 for k balls as freq[0] will be 1.
So,
k x 1=k.
otherwise will get 0

I think you mean (freq[i]*(freq[i]-1)) / 2

I am getting wrong answer. But it is right for test cases

[dhayden]

Are lines 27-32 correct? If i==k/2 then you choose 2 boxes from freq[i]. So if X=freq[i] then it's X! / (2! * (X-2)!) == X*(X-1)/2 ... I think....

[1vf9z8AR]

@dhayden

suppose I have 3 3 3 3 and k is 6
then
no of combinations is 3+2+1=6 where freq[3]=4 and start=4-1=3

[ne555]

> I am doing freq[0]=1 for k balls as freq[0] will be 1.
> So,
> k x 1=k.
> otherwise will get 0
¿is that correct? ¿do you may select just one box or do you need to always get two?
perhaps 0 is the correct answer

> I think you mean (freq[i]*(freq[i]-1)) / 2
yes, my bad

[1vf9z8AR]

@ne555

Oh yes, this was the issue. selection of one box was not allowed.
thankyou:)