In this HackerEarth Countries Grouping problem solution People in the group, are sitting in a row numbered from 1 to N. Every person have been asked the same question as

How many people from your country are there in the group?

The answers provided may be incorrect. It is known that people of the same countries always sit together. If all the given answers are correct, determine the number of distinct countries present otherwise print "Invalid Data".


HackerEarth Countries Grouping problem solution


HackerEarth Countries Grouping problem solution.

#include<bits/stdc++.h>
using namespace std;
const int INVALID_DATA = 1000000007;
int main(){
    FILE *fin = freopen("Countries_Grouping_Input/in11.txt", "r", stdin);
  assert( fin!=NULL );
  FILE *fout = freopen("out11.txt", "w", stdout);
    int T;
    cin>>T;
    while(T--){
        int N;
        cin>>N;
        int answer[N];
        for(int i=0;i<N;i++){
            cin>>answer[i];
        }
        int index=0;
        int distinct_countries = 0; //Count for distinct countries

        while(index<N){
            distinct_countries++;
            int cnt = answer[index];
            if(index+cnt>N){
                // Not enough people
                distinct_countries = INVALID_DATA;
                break;
            }
            for(int j=index;j<index+cnt;j++){
                if(answer[j]!=cnt){
                    distinct_countries = INVALID_DATA;
                    break;
                }
            }
            if(distinct_countries==INVALID_DATA)    break;
            index+=cnt;
        }
        if(distinct_countries==INVALID_DATA){
            cout<<"Invalid Data\n";
        }
        else{
            cout<<distinct_countries<<"\n";
        }
    }
    return 0;
}

Second solution

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define irep(i,a,b) for (int i=a;i>=b;i--)
#define pii pair <int, int>
#define pll pair <ll,ll>

using namespace std;
const int ma = 1e5+5;
int a[ma];
int main(int argc, char* argv[])
{
  if(argc == 2 or argc == 3) 
     freopen(argv[1], "r", stdin);
  if(argc == 3) 
     freopen(argv[2], "w", stdout);
  ios::sync_with_stdio(false);
  int t;
  cin>>t;
  for(int p=0;p<t;p++)
  {
    int n;
    cin>>n;
    bool f=false;
    rep(i,1,n)
    {
      cin>>a[i];
    }
    int i=1;
    int ans=0;
    while(i<=n)
    {
      int j,c=0;
      for(j=i;j<min(i+a[i],n+1);j++)
      {
        if(a[j]!=a[i])
        {
          f=true;
          break;
        }
        c++;
      }
      if(c!=a[i])
      {
        f=true;
        break;
      }
      i = j;
      ans++;
    }
    if(f)
      cout<<"Invalid Data"<<endl;
    else
      cout<<ans<<endl;
  }
  return 0;
}