CRNVALEN

The Valentine Confession

Link to the question :  CRNVALEN

HINTS :

The question asks us to find out the number of girls who are double dating. First we take the input a[ ] of all the girls, say, n. Then we sort it. Now, if all the elements of a[ ] are equal and and equal to n-1, then all the girls are double dating. This can be very easily imagined.

If the last element of the array  is greater than or equal to n, then the output is -1 as this is not possible.

Now if both the cases are not true, then the answer will be the last element of the array or the maximum number. But we need to check again if the girls are fooling. So for that we can keep a counter such that if c is the number of girls double dating then, c girls will say c-1 as their response and n-c girls will give c girls as their answer. Hence, c is the output.

SOURCE CODE :

/* The Valentine Confession */

/* Sushant Gupta */







#include<stdio.h>

#include<algorithm>

using namespace std;

int main()

{

     int t;

     scanf("%d",&t);

     while(t--)

     {





    int n,f=0;

    scanf("%d",&n);

    long long int  i,ans,a[n],c1=0,c2=0;

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

        scanf("%lld",&a[i]);

    sort(a,a+n);

    if(a[n-1] > n-1)

    {



          //printf("-1");

            f= 0;

    }

    else if(a[n-1] == a[0] && a[0]== n-1)

    {

        //printf("%d",n);

        ans = n;

        f = 1;

    }

    else {

            ans = a[n-1];

            c1 = ans;

            c2 = n - ans;

          for(i=n-1;i>=0;i--)

          {

                         if(a[i] == ans)

                            c2--;

                         else if(a[i] == ans-1)

                            c1--;

          }

          if(c1 ==c2  && c2 == 0 )

          {

              // printf("%d",ans);

              f = 1;

          }

          else

          {

              //printf("-1");

              f =0;

          }

    }

    if(f==0)

        printf("-1\n");

    else

        printf("%lld\n",ans);

     }

    return 0;

}