Encuentre elementos mínimos después de considerar todas las transformaciones posibles

Dada una array de tres colores. Los elementos de la array tienen una propiedad especial. Cada vez que dos elementos de diferentes colores se vuelven adyacentes entre sí, se fusionan en un elemento del tercer color. ¿Cuántos números mínimos de elementos puede haber en la array después de considerar todas las transformaciones posibles?
Ejemplo: 

Input : arr[] = {R, G}
Output : 1
G B -> {G B} R -> R

Input : arr[] = {R, G, B}
Output : 2
Explanation : 
R G B -> [R G] B ->  B B
OR
R G B -> R {G B} ->  R R 

Escenarios

Antes de apresurarse a encontrar una solución, le sugerimos que pruebe diferentes ejemplos y vea si puede encontrar algún patrón. 
 

Let us see few more scenarios:
  1. R R R, Output 3
  2. R R G B -> R [R G] B -> [R B] B -> [G B] -> R, Output 1
  3. R G R G -> [R G] R G -> [B R] G ->G G, Output 2
  4. R G B B G R -> R [G B] B G R ->R [R B] G R ->[R G] G R 
                    -> [B G] R ->R R, Output 2
  5. R R B B G -> R [R B] [B G] -> R [G R] -> [R B] -> G,
                     Output 1

¿Encontraste algún patrón en la salida? 
 

Patrones posibles

Sea n el número de elementos del arreglo. No importa cuál sea la entrada, siempre terminamos en tres tipos de salidas: 
 

• n: Cuando no puede tener lugar ninguna transformación
• 2: Cuando el número de elementos de cada color son todos impares o todos pares
• 1: cuando el número de elementos de cada color es una mezcla de pares e impares

Pasos: 

1) Count the number of elements of each color.
2) Then only one out of the following four cases can happen:
......1) There are elements of only one color, return n.
......2) There are even number of elements of each color, return 2.
......3) There are odd number of elements of each color, return 2.
......4) In every other case, return 1.
        (The elements will combine with each other repeatedly until 
         only one of them is left)

A continuación se muestra la implementación del algoritmo anterior.
 

// C++ program to find count of minimum elements
// after considering all possible transformations.
#include <iostream>
using namespace std;
 
// Returns minimum possible elements after considering
// all possible transformations.
int findMin(char arr[], int n)
{
    // Initialize counts of all colors as 0
    int b_count = 0, g_count = 0, r_count = 0;
 
    // Count number of elements of different colors
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 'B') b_count++;
        if (arr[i] == 'G') g_count++;
        if (arr[i] == 'R') r_count++;
    }
 
    // Check if elements are of same color
    if (b_count==n || g_count==n || r_count==n)
        return n;
 
    // If all are odd, return 2
    if ((r_count&1 && g_count&1 && b_count&1) )
        return 2;
 
    // If all are even, then also return 2
    if (!(r_count & 1) && !(g_count & 1) &&
        !(b_count & 1) )
        return 2;
 
    // If none above the cases are true, return 1
    return 1;
}
 
// Driver code
int main()
{
    char arr[] = {'R', 'G', 'B', 'R'};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << findMin(arr, n);
    return 0;
}

import java.util.*;
 
// Java program to find count of minimum elements
// after considering all possible transformations.
class solution
{
 
// Returns minimum possible elements after considering
// all possible transformations.
static int findMin(char arr[], int n)
{
    // Initialize counts of all colors as 0
    int b_count = 0, g_count = 0, r_count = 0;
 
    // Count number of elements of different colors
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 'B') b_count++;
        if (arr[i] == 'G') g_count++;
        if (arr[i] == 'R') r_count++;
    }
 
    // Check if elements are of same color
    if (b_count==n || g_count==n || r_count==n)
        return n;
 
    // If all are odd, return 2
    if((r_count&1) == 1)    {
     if((g_count&1) == 1)     {
      if((b_count&1) == 1)
        return 2;
     }
    }
 
    // If all are even, then also return 2
    if((r_count & 1) == 0)
    {
      if ((g_count & 1) == 0)
      {
          if ((b_count & 1) == 0)
                return 2;
      }
    }
 
    // If none above the cases are true, return 1
    return 1;
}
 
// Driver code
public static void main(String args[])
{
    char arr[] = {'R', 'G', 'B', 'R'};
    int n = arr.length;
    System.out.println(findMin(arr, n));
     
}
}
// This code is contributed byte
// Surendra_Gangwar

# Python 3 program to find count of minimum elements
# after considering all possible transformations.
 
# Returns minimum possible elements after
# considering all possible transformations.
def findMin(arr, n):
 
    # Initialize counts of all
    # colors as 0
    b_count = 0
    g_count = 0
    r_count = 0
 
    # Count number of elements of
    # different colors
    for i in range(n):
        if (arr[i] == 'B'):
            b_count += 1
        if (arr[i] == 'G'):
            g_count += 1
        if (arr[i] == 'R'):
            r_count += 1
             
    # Check if elements are of same color
    if (b_count == n or
        g_count == n or r_count == n):
        return n
 
    # If all are odd, return 2
    if ((r_count&1 and
         g_count&1 and b_count&1)):
        return 2
 
    # If all are even, then also return 2
    if (not (r_count & 1) and not
            (g_count & 1) and not (b_count & 1)):
        return 2
 
    # If none above the cases
    # are true, return 1
    return 1
 
# Driver code
if __name__ == "__main__":
     
    arr = ['R', 'G', 'B', 'R']
    n = len(arr)
    print(findMin(arr, n))
 
# This code is contributed
# by ChitraNayal

// C# program to find count of minimum elements
// after considering all possible transformations.
using System;
 
class GFG
{
 
// Returns minimum possible elements after
// considering all possible transformations.
static int findMin(char []arr, int n)
{
    // Initialize counts of all colors as 0
    int b_count = 0, g_count = 0, r_count = 0;
 
    // Count number of elements of different colors
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 'B') b_count++;
        if (arr[i] == 'G') g_count++;
        if (arr[i] == 'R') r_count++;
    }
 
    // Check if elements are of same color
    if (b_count == n || g_count == n || r_count == n)
        return n;
 
    // If all are odd, return 2
    if((r_count&1) == 1)
    {
        if((g_count&1) == 1)   
        {
            if((b_count&1) == 1)
                return 2;
        }
    }
 
    // If all are even, then also return 2
    if((r_count & 1) == 0)
    {
        if ((g_count & 1) == 0)
        {
            if ((b_count & 1) == 0)
                    return 2;
        }
    }
 
    // If none above the cases are true,
    // return 1
    return 1;
}
 
// Driver code
public static void Main()
{
    char []arr = {'R', 'G', 'B', 'R'};
    int n = arr.Length;
    Console.WriteLine(findMin(arr, n));
}
}
 
// This code is contributed byte
// nitin mittal

<?php
// PHP program to find count of minimum elements
// after considering all possible transformations.
 
// Returns minimum possible elements after
// considering all possible transformations.
function findMin($arr, $n)
{
    // Initialize counts of all colors as 0
    $b_count = 0; $g_count = 0; $r_count = 0;
 
    // Count number of elements of
    // different colors
    for ($i = 0; $i < $n; $i++)
    {
        if ($arr[$i] == 'B') $b_count++;
        if ($arr[$i] == 'G') $g_count++;
        if ($arr[$i] == 'R') $r_count++;
    }
 
    // Check if elements are of same color
    if ($b_count == $n || $g_count == $n ||
                          $r_count == $n)
        return $n;
 
    // If all are odd, return 2
    if (($r_count & 1 && $g_count & 1 &&
                         $b_count & 1))
        return 2;
 
    // If all are even, then also return 2
    if (!($r_count & 1) && !($g_count & 1) &&
        !($b_count & 1) )
        return 2;
 
    // If none above the cases are
    // true, return 1
    return 1;
}
 
// Driver code
$arr = array('R', 'G', 'B', 'R');
$n = count($arr);
echo findMin($arr, $n);
 
// This code is contributed by 29AjayKumar
?>

<script>
// Javascript program to find count of minimum elements
// after considering all possible transformations.
     
    // Returns minimum possible elements after considering
    // all possible transformations.
    function findMin(arr,n)
    {
     
        // Initialize counts of all colors as 0
        let b_count = 0, g_count = 0, r_count = 0;
      
        // Count number of elements of different colors
        for (let i = 0; i < n; i++)
        {
            if (arr[i] == 'B') b_count++;
            if (arr[i] == 'G') g_count++;
            if (arr[i] == 'R') r_count++;
        }
      
        // Check if elements are of same color
        if (b_count==n || g_count==n || r_count==n)
            return n;
      
        // If all are odd, return 2
        if((r_count&1) == 1)    {
         if((g_count&1) == 1)     {
          if((b_count&1) == 1)
            return 2;
         }
        }
      
        // If all are even, then also return 2
        if((r_count & 1) == 0)
        {
          if ((g_count & 1) == 0)
          {
              if ((b_count & 1) == 0)
                    return 2;
          }
        }
      
        // If none above the cases are true, return 1
        return 1;
    }
     
    // Driver code
    let arr=['R', 'G', 'B', 'R'];
    let n = arr.length;
    document.write(findMin(arr, n));
     
    // This code is contributed by rag2127.
</script>

Producción : 

1

Complejidad temporal: O(n) 
Espacio auxiliar: O(1)
Ejercicio: 
 

1. ¿Cuántas transformaciones se necesitan en el problema anterior?
2. ¿Es posible imprimir la secuencia en la que se transforman los elementos? En caso afirmativo, ¿cuál será el enfoque? Discutir la complejidad del tiempo y el espacio.

Este artículo es una contribución de Aashish Barnwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.