Número mínimo de colores necesarios para colorear una array circular

Dada una array circular arr[] que contiene N enteros, la tarea es encontrar el número mínimo de colores necesarios para colorear el elemento de la array de modo que dos elementos adyacentes que tengan valores diferentes no deben tener el mismo color.
Ejemplos: 
 

Entrada: arr[] = {1, 2, 1, 1, 2} 
Salida: 2 
Explicación: 
Se requiere un mínimo de 2 tipos de colores. 
Podemos distribuir el color como {r, g, r, r, g} de manera que ningún elemento adyacente que tenga un valor diferente tenga el mismo color.
Entrada: arr[] = {1, 2, 3, 4} 
Salida: 2 
Explicación: 
Se requiere un mínimo de 2 tipos de colores. 
Podemos distribuir el color como {r, g, r, g}. 
 

Enfoque: este problema se puede resolver utilizando el enfoque codicioso . 
 

1. Si todos los valores son iguales, solo se requiere 1 color.
2. Si hay más de un elemento distinto y el número total de elementos es par, se requieren 2 colores.
3. Si hay más de un elemento distinto y el número total de elementos es impar, compruebe: 
   • Si existen elementos adyacentes que tienen el mismo valor, entonces se requieren 2 colores.
   • Se requieren otros 3 colores.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ code for the above approach
#include<bits/stdc++.h>
using namespace std;
 
int main(){
    vector<int>lst = {1,2,3,3,4,5,5};
    bool flag1 = true ;
    bool flag_adj = false;
    int count = 0;
    int count_color = 0;
    for(int i = 0; i < lst.size() - 1; i++)
    {
        if(lst[i] != lst[i + 1])
            flag1 = false;
        else
            count += 1;
    }
    if(flag1 == true)
        count_color = 1;
    else{
        if((lst.size()-count)%2 != 0)
            count_color = 3;
        else
            count_color = 2;
    }
    cout << count_color << "\n";
    return 0;
}
 
// This code is contributed by Taranpreet

lst=[1,2,3,3,4,5,5]
flag1=True
flag_adj=False
count=0
for i in range(len(lst)-1):
    if lst[i]!=lst[i+1]:
        flag1=False
    else:
        count+=1
if flag1==True:
    count_color=1
else:
    if (len(lst)-count)%2:
        count_color=3
    else:
        count_color=2
print(count_color)

<script>
 
let lst = [1,2,3,3,4,5,5]
let flag1 = true
let flag_adj = false
let count = 0
for(let i = 0; i < lst.length - 1; i++)
{
    if(lst[i] != lst[i + 1])
        flag1 = false
    else
        count += 1
}
if(flag1 == true)
    count_color = 1
else{
    if((lst.length-count)%2)
        count_color = 3
    else
        count_color = 2
}
document.write(count_color)
 
// This code is contributed by shinjanpatra
 
</script>

Complejidad temporal: O(N) , donde N es el número de elementos.