Find an arrangement of M colors for N indices such that no two adjacent indices have same color and each color can be used at most K times. If no such arrangement exists, output -1.
Examples:
Input: N = 6, M = 4, K = 2
Output: 1 2 3 4 1 2
Explanation: Color 1 is assigned to the 1-st index.
Color 2 is assigned to the 2-nd index, color 3 to the 3-rd index,
color 4 to the 4-th index.
Again, color 1 is assigned to 5-th index and color 2 to 6-th index.Input: N = 20, M = 6, K = 3
Output: -1
Explanation: No such arrangement exists in which 6 colors may be assigned to at most 3 indices.
Approach: Observe the following points:
- If the number of colors is only 1 and the number of indices is greater than 1, then no such assignment can exist.
- If the total number of indices is greater than what can be colored by the colors available (M*K), then no such assignment exists.
Follow the steps below to solve the above problem:
- If the number of colors is 1 and the number of indices is greater than 1, then output -1.
- If the total number of colors is greater than what can be colored by the available colors (M*K), then output -1.
- If both of the above conditions do not meet, then:
- Initialize variable x with 1.
- Run a loop till N and within the loop, output x. Increment x and check if x is greater than M. If x becomes greater than M, set x = 1.
- When x is set to 1, the loop again starts printing the number of colors from 1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to find the required // arrangement of colors to indicesvoid 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 Codeint main(){ // Given input int N = 6, M = 4, K = 2; // Function Call findAssignment(N, M, K); return 0;} |
Java
// Java program for the above approachimport 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 |
Python3
# Python code for the above approach # Function to find the required # arrangement of colors to indicesdef 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 inputN = 6M = 4K = 2# Function CallfindAssignment(N, M, K);# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the required // arrangement of colors to indicesstatic 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 Codepublic 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. |
Javascript
<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> |
Output
1 2 3 4 1 2
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
