Tuesday, 1 September 2020

Countries Grouping Hacker Earth Solution in C

 https://www.hackerearth.com/practice/basic-programming/implementation/basics-of-implementation/practice-problems/algorithm/countries-grouping-1-5b13620a/editorial/


Explanation copied from editorial

If we start analyzing the answer of first person then there must be that number of people after him(including him) and all of their answers must be same as the first person's.

Let, answer[0] is 7. Then, this also means that answer[0], answer[1], answer[2], answer[3], answer[4], answer[5] and answer[6] must exist and each be 7. So, from answer[7] onwards, same algorithm can be applied to check the authenticity of the data provided and answer[7] will be considered as the starting index for the next country. After checking validity of the data, if it's invalid the answer is "Invalid Data" otherwise the distinct_countries count is incremented by 1 and when finally all of the people's responses are checked to be valid, the answer is calculated as distinct_countries.


#include<stdio.h>
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int a[n],i,j,c,flag=0;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
int dc = 0;
for(i=0;i<n;i=i+c)
        {
dc++;
c = a[i];
if(i+c>n)
            {
flag = 1;
break;
}
for(j=i;j<i+c;j++)
            {
if(a[j]!=c)
                {
flag = 1;
break;
}
}
if(flag==1)
                break;
}
if(flag==1)
            printf("Invalid Data\n");
else
printf("%d\n",dc);
}
}

No comments:

Post a Comment