Agrupación de países

Las personas en un grupo están sentadas en fila numeradas del 1 al n. A todos se les ha hecho la misma pregunta, «¿Cuántas personas de tu país hay en el grupo?» 
Las respuestas proporcionadas por las personas pueden ser incorrectas. Las personas del mismo país siempre se sientan juntas. Si todas las respuestas son correctas, determine el número de países distintos; de lo contrario, imprima «Respuesta no válida».

Ejemplos:  

Input : ans[] = {1, 3, 2, 2}
Output : Invalid Answer
The second person says there are 3 
people from his country however
the person sitting next to him says
there are 2 people. Hence this is 
an invalid answer. 

Input : ans[] = {1, 1, 2, 2, 4, 4, 
                            4, 4}
Output : 4
There are 1 person each representing
two distinct countries. In the next 
one there are two people and in the
fourth one there are 4 people from
the same country.

Fuente: Prueba de calificación de aplicaciones de ThoughtWorks 

Este es un problema básico que se puede resolver en tiempo lineal. Tomaremos una variable curr_size que nos dice el tamaño del país actual que se está considerando. Cualquiera que sea el tamaño, el siguiente número de personas del ‘tamaño’ debe dar la misma respuesta para que se forme un grupo válido. Si alguien da una respuesta diferente o hay menos de esa cantidad de personas disponibles, entonces la respuesta es Inválida. A continuación se muestra la implementación de la idea: 

// CPP program to count no of distinct
// countries from a given group of people
#include <iostream>
using namespace std;
 
void countCountries(int ans[], int N)
{
    int total_countries = 0, i = 0;
    bool invalid = false;
 
    while (i < N) {
        int curr_size = ans[i];
 
        // Answer is valid if adjacent sitting
        // num people give same answer
        int num = ans[i];
        while (num > 0) {
 
            // someone gives different answer
            if (ans[i] != curr_size) {
                cout << "Invalid Answer\n";
                return;
            }
            else
                num--;
 
            // check next person
            i++;
        }
 
        // one valid country group has
        // been found
        total_countries++;
    }
 
    cout << "There are " << total_countries
         << " distinct companies in the group.\n";
}
 
// driver program to test above function
int main()
{
    int ans[] = { 1, 1, 2, 2, 4, 4, 4, 4 };
    int n = sizeof(ans) / sizeof(ans[0]);
    countCountries(ans, n);
    return 0;
}

// Java program to count no of distinct
// countries from a given group of people
 
class Country
{
    public static void countCountries(int ans[],
                                      int N)
    {
        int total_countries = 0, i = 0;
        boolean invalid = false;
 
        while (i < N) {
            int curr_size = ans[i];
 
            // Answer is valid if adjacent sitting
            // num people give same answer
            int num = ans[i];
            while (num > 0) {
 
            // someone gives different answer
            if (ans[i] != curr_size) {
                System.out.print( "Invalid Answer\n" );
                return;
            }
            else
                num--;
 
            // check next person
            i++;
        }
 
        // one valid country group has
        // been found
        total_countries++;
        }
 
        System.out.print( "There are " + total_countries +
            " distinct companies in the group.\n" );
    }
 
    // driver code
    public static void main(String[] args)
    {
        int ans[] = { 1, 1, 2, 2, 4, 4, 4, 4 };
        int n = 8;
        countCountries(ans, n);
    }
}
 
// This code is contributed by rishabh_jain

# Python3 program to count no of distinct
# countries from a given group of people
 
def countCountries(ans, N):
    total_countries = 0
    i = 0
    invalid = 0
 
    while (i < N) :
        curr_size = ans[i]
 
        # Answer is valid if adjacent sitting
        # num people give same answer
        num = ans[i]
        while (num > 0) :
 
            # someone gives different answer
            if (ans[i] != curr_size) :
                print("Invalid Answer")
                return;
            else:
                num = num - 1
 
            # check next person
            i = i + 1
 
        # one valid country group has
        # been found
        total_countries = total_countries + 1;
 
    print ("There are ", total_countries,
          " distinct companies in the group.")
 
# Driven code
ans = [ 1, 1, 2, 2, 4, 4, 4, 4 ];
n = len(ans);
countCountries(ans, n);
 
# This code is contributed by "rishabh_jain".

// C# program to count no. of distinct
// countries from a given group of people
using System;
 
class Country {
     
    // function to count no. of distinct
    // countries from a given group of people
    public static void countCountries(int []ans,
                                      int N)
    {
        int total_countries = 0, i = 0;
 
 
        while (i < N) {
            int curr_size = ans[i];
 
            // Answer is valid if adjacent sitting
            // num people give same answer
            int num = ans[i];
            while (num > 0) {
 
            // someone gives different answer
            if (ans[i] != curr_size) {
                Console.Write( "Invalid Answer\n" );
                return;
            }
            else
                num--;
 
            // check next person
            i++;
        }
 
        // one valid country group
        // has been found
        total_countries++;
        }
 
        Console.Write("There are " + total_countries +
                      " distinct companies in the group.\n" );
    }
 
    // Driver Code
    public static void Main()
    {
        int []ans = { 1, 1, 2, 2, 4, 4, 4, 4 };
        int n = 8;
        countCountries(ans, n);
    }
}
 
// This code is contributed by nitin mittal

<?php
// PHP program to count no of distinct
// countries from a given group of people
 
function countCountries($ans, $N)
{
    $total_countries = 0;
    $i = 0;
    $invalid = false;
 
    while ($i < $N)
    {
        $curr_size = $ans[$i];
 
        // Answer is valid if adjacent sitting
        // num people give same answer
        $num = $ans[$i];
        while ($num > 0)
        {
 
            // someone gives different
            // answer
            if ($ans[$i] != $curr_size)
            {
                echo"Invalid Answer\n";
                return;
            }
            else
                $num--;
 
            // check next person
            $i++;
        }
 
        // one valid country group has
        // been found
        $total_countries++;
    }
 
    echo "There are " , $total_countries
        , " distinct companies in the group.\n";
}
 
    // Driver Code
    $ans = array(1, 1, 2, 2, 4, 4, 4, 4 );
    $n = sizeof($ans);
    countCountries($ans, $n);
     
// This code is contributed by nitin mittal.
?>

<script>
 
// JavaScript program to count no of distinct
// countries from a given group of people
function countCountries(ans, N)
{
    let total_countries = 0, i = 0;
    let invalid = false;
 
    while (i < N)
    {
        let curr_size = ans[i];
 
        // Answer is valid if adjacent sitting
        // num people give same answer
        let num = ans[i];
        while (num > 0)
        {
             
            // Someone gives different answer
            if (ans[i] != curr_size)
            {
                document.write( "Invalid Answer\n" );
                return;
            }
            else
                num--;
     
            // Check next person
            i++;
        }
         
        // One valid country group has
        // been found
        total_countries++;
    }
    document.write("There are " + total_countries +
                   " distinct companies in the group.\n" );
}
 
// Driver Code
let ans = [ 1, 1, 2, 2, 4, 4, 4, 4 ];
let n = 8;
 
countCountries(ans, n);
 
// This code is contributed by sanjoy_62  
 
</script>

Producción: 

There are 4 distinct companies in the group.