Compruebe si los N índices de la array dada se pueden colorear con M colores usando un color como máximo K veces

Encuentre una disposición de M colores para N índices tal que no haya dos índices adyacentes que tengan el mismo color y cada color se pueda usar como máximo K veces. Si no existe tal arreglo, salida -1.

Ejemplos:

Entrada: N = 6, M = 4, K = 2
Salida: 1 2 3 4 1 2 
Explicación: El color 1 se asigna al primer índice. 
El color 2 se asigna al 2º índice, el color 3 al 3º índice, 
el color 4 al 4º índice. 
De nuevo, el color 1 se asigna al índice 5 y el color 2 al índice 6.

Entrada: N = 20, M = 6, K = 3
Salida: -1
Explicación: No existe tal disposición en la que se puedan asignar 6 colores a un máximo de 3 índices.

Enfoque: Observe los siguientes puntos:

• Si el número de colores es solo 1 y el número de índices es mayor que 1, entonces no puede existir tal asignación.
• Si el número total de índices es mayor que lo que se puede colorear con los colores disponibles ( M * K ), entonces no existe tal asignación.

Siga los pasos a continuación para resolver el problema anterior:

• Si el número de colores es 1 y el número de índices es mayor que 1, la salida es -1.
• Si el número total de colores es mayor que lo que se puede colorear con los colores disponibles ( M * K ), entonces genera -1.
• Si las dos condiciones anteriores no se cumplen, entonces:
  • Inicialice la variable x con 1.
  • Ejecute un ciclo hasta N y dentro del ciclo, genere x . Incremente x y verifique si x es mayor que M . Si x se vuelve mayor que M , establezca x = 1.
  • Cuando x se establece en 1, el ciclo nuevamente comienza a imprimir el número de colores desde 1.

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

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function to find the required
// arrangement of colors to indices
void findAssignment(int N, int M, int K)
{
    // If number of colors is 1
    // and number of indices is more than 1
    if (M == 1 && N > 1) {
 
        // Output -1
        cout << -1;
    }
 
    // If number of indices is more than
    // what can be colored
    // by the available colors
    else if (N > M * K) {
 
        // Output -1
        cout << -1;
    }
    else {
 
        // Initialize x with 1
        int x = 1;
 
        // Loop to print
        // the required arrangement
        for (int i = 0; i < N; ++i) {
 
            // Output the number of colors
            cout << x << " ";
 
            // Increment the number of colors
            x++;
 
            // If x exceeds the total number
            // of available colors
            if (x > M) {
 
                // Set x to 1
                x = 1;
            }
        }
    }
}
 
// Driver Code
int main()
{
    // Given input
    int N = 6, M = 4, K = 2;
 
    // Function Call
    findAssignment(N, M, K);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to find the required
  // arrangement of colors to indices
  static void findAssignment(int N, int M, int K)
  {
 
    // If number of colors is 1
    // and number of indices is more than 1
    if (M == 1 && N > 1) {
 
      // Output -1
      System.out.print("-1");
    }
 
    // If number of indices is more than
    // what can be colored
    // by the available colors
    else if (N > M * K) {
 
      // Output -1
      System.out.print("-1");
    }
    else {
 
      // Initialize x with 1
      int x = 1;
 
      // Loop to print
      // the required arrangement
      for (int i = 0; i < N; ++i) {
 
        // Output the number of colors
        System.out.print(x + " ");
 
        // Increment the number of colors
        x++;
 
        // If x exceeds the total number
        // of available colors
        if (x > M) {
 
          // Set x to 1
          x = 1;
        }
      }
    }
  }
 
  // Driver Code
  public static void main (String[] args)
  {
 
    // Given input
    int N = 6, M = 4, K = 2;
 
    // Function Call
    findAssignment(N, M, K);
  }
}
 
// This code is contributed by hrithikgarg03188

# Python code for the above approach
 
# Function to find the required
# arrangement of colors to indices
def findAssignment(N, M, K):
 
    # If number of colors is 1
    # and number of indices is more than 1
    if (M == 1 and N > 1):
 
        # Output -1
        print(-1)
     
    # If number of indices is more than
    # what can be colored
    # by the available colors
    elif (N > M * K) :
 
        # Output -1
        print(-1)
     
    else:
 
        # Initialize x with 1
        x = 1;
 
        # Loop to print
        # the required arrangement
        for i in range(N):
 
            # Output the number of colors
            print(x, end= " ");
 
            # Increment the number of colors
            x += 1
 
            # If x exceeds the total number
            # of available colors
            if (x > M):
 
                # Set x to 1
                x = 1;
 
# Driver Code
 
# Given input
N = 6
M = 4
K = 2
 
# Function Call
findAssignment(N, M, K);
 
# This code is contributed by gfgking

// C# program for the above approach
using System;
class GFG
{
   
// Function to find the required
// arrangement of colors to indices
static void findAssignment(int N, int M, int K)
{
   
    // If number of colors is 1
    // and number of indices is more than 1
    if (M == 1 && N > 1) {
 
        // Output -1
        Console.Write(-1);
    }
 
    // If number of indices is more than
    // what can be colored
    // by the available colors
    else if (N > M * K) {
 
        // Output -1
        Console.Write(-1);
    }
    else {
 
        // Initialize x with 1
        int x = 1;
 
        // Loop to print
        // the required arrangement
        for (int i = 0; i < N; ++i) {
 
            // Output the number of colors
            Console.Write(x + " ");
 
            // Increment the number of colors
            x++;
 
            // If x exceeds the total number
            // of available colors
            if (x > M) {
 
                // Set x to 1
                x = 1;
            }
        }
    }
}
 
// Driver Code
public static void Main()
{
   
    // Given input
    int N = 6, M = 4, K = 2;
 
    // Function Call
    findAssignment(N, M, K);
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to find the required
       // arrangement of colors to indices
       function findAssignment(N, M, K)
       {
        
           // If number of colors is 1
           // and number of indices is more than 1
           if (M == 1 && N > 1) {
 
               // Output -1
               document.write(-1)
           }
 
           // If number of indices is more than
           // what can be colored
           // by the available colors
           else if (N > M * K) {
 
               // Output -1
               document.write(-1)
           }
           else {
 
               // Initialize x with 1
               let x = 1;
 
               // Loop to print
               // the required arrangement
               for (let i = 0; i < N; ++i) {
 
                   // Output the number of colors
                   document.write(x + " ");
 
                   // Increment the number of colors
                   x++;
 
                   // If x exceeds the total number
                   // of available colors
                   if (x > M) {
 
                       // Set x to 1
                       x = 1;
                   }
               }
           }
       }
 
       // Driver Code
 
       // Given input
       let N = 6, M = 4, K = 2;
 
       // Function Call
       findAssignment(N, M, K);
 
        // This code is contributed by Potta Lokesh
   </script>

1 2 3 4 1 2 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)