K3003 Editorial Pairs

editorial
1

Problem : Pairs
Problem code : K3003
Problem Link : Pairs | CodeChef
Difficulty : Medium

Prerequisites : Basic Maths, combinatorics and hashing.

Problem :
Numbers of pair in array such that a*b < a+b.

Explanation :
1.) First of all you need to find number of 0,number of 1 and number of elements is array other than 0 and 1.
2.) Let x be the number of 0, y be the number of 1 and z be the number of elements in array other than 0 and 1.
3.) 0temp = 0 is always less than 0 + temp = temp if(temp>0) so number of pairs of (0,temp) will be x(y+z).
4.) 1temp = temp is always less than 1 + temp here temp is greater than 0 as we already include all pairs of (1,0) in 3rd point so number of pairs for each 1 will be (1,number of elements next to 1).
5.) Note pair (1,1) is also included as 11 < 1+1.

Code:

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        ll i,j,k,l=0,x=0,y=0,z=0,n,sum=0;
        //string s;
        vector<ll> v(1);
        cin>>n;
        for(i=1;i<=n;i++)
        {
            cin>>k;
            if(k==0)
            x++;
            else if(k==1)
            y++;
            else
            z++;
        }
        sum = sum + x*(y+z);
        k=y;
        for(i=1;i<=y;i++)
        {
            k--;
            sum = sum + (k+z);
        }
        cout<<sum<<"\n";
    }
    
}
1 Like