Dada una array arr[] que consta de N enteros positivos, la tarea es verificar si es posible colorear los N objetos de manera que para el i -ésimo elemento de la array existan exactamente arr[i] colores distintos utilizados para colorear todos los objetos excepto para el i -ésimo objeto.
Ejemplos:
Entrada: arr[] = {1, 2, 2}
Salida: Sí
Explicación:
Una de las formas posibles de colorear es: {“Rojo”, “azul”, “azul”}.
- Para arr[0](=1), hay exactamente 1 color distinto, que es «azul».
- Para arr[1](=2), hay exactamente 2 colores distintos, que son «azul» y «rojo».
- Para arr[2](=3), hay exactamente 2 colores distintos, que son «azul» y «rojo».
Entrada: arr[] = {4, 3, 4, 3, 4}
Salida: No
Enfoque: El problema se puede resolver con base en las siguientes observaciones:
- Para 2 objetos, hay N-2 objetos comunes al calcular el número de colores distintos. Por lo tanto, puede haber una diferencia de como máximo 1 entre el elemento máximo y mínimo de la array arr[].
- Ahora hay dos casos:
- Si los elementos máximo y mínimo son iguales, entonces la respuesta es “Sí”, solo si el elemento es N – 1 o el elemento es menor o igual a N/2 , porque cada color se puede usar más de una vez.
- Si la diferencia entre el elemento máximo y mínimo es 1 , entonces el número de colores distintos en el objeto N debe ser igual al elemento máximo, porque el elemento mínimo es 1 menos que el elemento máximo.
- Ahora, asumiendo que la frecuencia del elemento mínimo es X y la frecuencia del elemento máximo es Y , entonces la respuesta es » Sí » si y solo si X+1 ≤ A ≤ X+ Y/2 (basado en observación).
Siga los pasos a continuación para resolver el problema:
- Primero ordene la array en orden ascendente.
- Si la diferencia entre arr[N-1] y arr[0] es mayor que 1, imprima “ No ”.
- De lo contrario, si arr[N-1] es igual a arr[0] , verifique lo siguiente:
- Si arr[N-1] = N-1 o 2*arr[N-1] <= N , entonces escriba “ Sí ”.
- De lo contrario, escriba “ No ”.
- De lo contrario, cuente las frecuencias de los elementos mínimo y máximo y guárdelos en variables, digamos X e Y , y luego haga lo siguiente:
- Si arr[N-1] es mayor que X y arr[N-1] es menor o igual que X+Y/2 , entonces escriba “ Sí ”.
- De lo contrario, escriba “ No ”.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if coloring is
// possible with give conditions
string checkValid(int arr[], int N)
{
// Sort the vector
sort(arr, arr + N);
// Coloring not possible in case of
// maximum - minimum element > 1
if (arr[N - 1] - arr[0] > 1)
return "No";
// case 1
else if (arr[N - 1] == arr[0]) {
// If h is equal to N-1 or
// N is greater than 2*h
if (arr[N - 1] == N - 1
|| 2 * arr[N - 1] <= N)
return "Yes";
else
return "No";
}
// Case 2
else {
// Stores frequency of minimum element
int x = 0;
for (int i = 0; i < N; i++) {
// Frequency of minimum element
if (arr[i] == arr[0])
x++;
}
// Stores frequency of maximum element
int y = N - x;
// Condition for case 2
if ((arr[N - 1] >= x + 1)
and (arr[N - 1] <= x + y / 2))
return "Yes";
else
return "No";
}
}
// Driver Code
int main()
{
// GivenInput
int arr[] = { 1, 2, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << checkValid(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check if coloring is
// possible with give conditions
static String checkValid(int arr[], int N)
{
// Sort the vector
Arrays.sort(arr);
// Coloring not possible in case of
// maximum - minimum element > 1
if (arr[N - 1] - arr[0] > 1)
return "No";
// Case 1
else if (arr[N - 1] == arr[0])
{
// If h is equal to N-1 or
// N is greater than 2*h
if (arr[N - 1] == N - 1
|| 2 * arr[N - 1] <= N)
return "Yes";
else
return "No";
}
// Case 2
else
{
// Stores frequency of minimum element
int x = 0;
for(int i = 0; i < N; i++)
{
// Frequency of minimum element
if (arr[i] == arr[0])
x++;
}
// Stores frequency of maximum element
int y = N - x;
// Condition for case 2
if ((arr[N - 1] >= x + 1) &&
(arr[N - 1] <= x + y / 2))
return "Yes";
else
return "No";
}
}
// Driver Code
public static void main(String[] args)
{
// Given Input
int[] arr = { 1, 2, 2 };
int N = arr.length;
// Function Call
System.out.print(checkValid(arr, N));
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach # Function to check if coloring is # possible with give conditions def checkValid(arr, N): # Sort the vector arr = sorted(arr) # Coloring not possible in case of # maximum - minimum element > 1 if (arr[N - 1] - arr[0] > 1): return "No" # case 1 elif (arr[N - 1] == arr[0]): # If h is equal to N-1 or # N is greater than 2*h if (arr[N - 1] == N - 1 or 2 * arr[N - 1] <= N): return "Yes" else: return "No" # Case 2 else: # Stores frequency of minimum element x = 0 for i in range(N): # Frequency of minimum element if (arr[i] == arr[0]): x += 1 # Stores frequency of maximum element y = N - x # Condition for case 2 if ((arr[N - 1] >= x + 1) and (arr[N - 1] <= x + y // 2)): return "Yes" else: return "No" # Driver Code if __name__ == '__main__': # Given Input arr = [ 1, 2, 2 ] N = len(arr) # Function Call print (checkValid(arr, N)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check if coloring is
// possible with give conditions
static string checkValid(int []arr, int N)
{
// Sort the vector
Array.Sort(arr);
// Coloring not possible in case of
// maximum - minimum element > 1
if (arr[N - 1] - arr[0] > 1)
return "No";
// case 1
else if (arr[N - 1] == arr[0]) {
// If h is equal to N-1 or
// N is greater than 2*h
if (arr[N - 1] == N - 1
|| 2 * arr[N - 1] <= N)
return "Yes";
else
return "No";
}
// Case 2
else {
// Stores frequency of minimum element
int x = 0;
for (int i = 0; i < N; i++) {
// Frequency of minimum element
if (arr[i] == arr[0])
x++;
}
// Stores frequency of maximum element
int y = N - x;
// Condition for case 2
if ((arr[N - 1] >= x + 1)
&& (arr[N - 1] <= x + y / 2))
return "Yes";
else
return "No";
}
}
// Driver Code
public static void Main()
{
// GivenInput
int []arr = { 1, 2, 2 };
int N = arr.Length;
// Function Call
Console.Write(checkValid(arr, N));
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// Javascript program for the above approach
// Function to check if coloring is
// possible with give conditions
function checkValid(arr, N)
{
// Sort the vector
arr.sort((a, b) => a - b);
// Coloring not possible in case of
// maximum - minimum element > 1
if (arr[N - 1] - arr[0] > 1)
return "No";
// Case 1
else if (arr[N - 1] == arr[0])
{
// If h is equal to N-1 or
// N is greater than 2*h
if (arr[N - 1] == N - 1 ||
2 * arr[N - 1] <= N)
return "Yes";
else
return "No";
}
// Case 2
else
{
// Stores frequency of minimum element
let x = 0;
for(let i = 0; i < N; i++)
{
// Frequency of minimum element
if (arr[i] == arr[0])
x++;
}
// Stores frequency of maximum element
let y = N - x;
// Condition for case 2
if ((arr[N - 1] >= x + 1) &&
(arr[N - 1] <= x + y / 2))
return "Yes";
else
return "No";
}
}
// Driver Code
// GivenInput
let arr = [ 1, 2, 2 ];
let N = arr.length;
// Function Call
document.write(checkValid(arr, N));
// This code is contributed by gfgking
</script>
Producción
Yes
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitpal210 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA