Проверить, можно ли N индексов данного массива раскрасить M цветами, используя один цвет не более K раз

Опубликовано: 20 Сентября, 2022

Найдите такое расположение M цветов для N индексов, что никакие два соседних индекса не имеют одного цвета и каждый цвет можно использовать не более K раз. Если такой договоренности не существует, выведите -1.

Примеры:

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.

Подход: обратите внимание на следующие моменты:

  • Если количество цветов равно 1, а количество индексов больше 1, то такого присвоения быть не может.
  • Если общее количество индексов больше, чем то, что можно раскрасить доступными цветами ( M * K ), то такого присвоения не существует.

Выполните следующие шаги, чтобы решить вышеуказанную проблему:

  • Если количество цветов равно 1 и количество индексов больше 1, то выведите -1.
  • Если общее количество цветов больше, чем можно раскрасить имеющимися цветами ( M * K ), то выведите -1.
  • Если оба вышеуказанных условия не выполняются, то:
    • Инициализируйте переменную x значением 1.
    • Запустите цикл до N и внутри цикла выведите x . Увеличьте x и проверьте, больше ли x , чем M . Если x становится больше, чем M , установите x = 1.
    • Когда для x установлено значение 1, цикл снова начинает печатать количество цветов, начиная с 1.

Ниже приведена реализация вышеуказанного подхода:


Сложность времени: НА)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ