Проверить, можно ли раскрасить N объектов так, чтобы для i-го объекта использовалось ровно arr[i] различных цветов.

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

Дан массив arr[] , состоящий из N положительных целых чисел, задача состоит в том, чтобы проверить, можно ли раскрасить N объектов так, чтобы для i -го элемента массива существовало ровно arr[i] различных цветов, использованных при окраске всех объектов. кроме i -го объекта.

Примеры:

Input: arr[] = {1, 2, 2}
Output: Yes
Explanation: 
One of the possible ways to color is:  {“Red”, “blue”, “blue”}.

  1. For arr[0](=1), there is exactly 1 distinct color, which is “blue”.
  2. For arr[1](=2), there are exactly 2 distinct colors, which are “blue” and “red”.
  3. For arr[2](=3), there are exactly 2 distinct colors, which are “blue” and “red”.

Input: arr[] = {4, 3, 4, 3, 4}
Output: No

Подход: Задача может быть решена на основе следующих наблюдений:

  1. For 2 objects, there are N-2 objects common while calculating the number of distinct colors. Therefore, there can be a difference of at most 1 between the maximum and minimum element of the array arr[].
  2. Now there are two cases:
    1. If the maximum and minimum elements are equal, then the answer is “Yes”,  only if the element is N – 1 or the element is less than or equal to N/2, because every color can be used more than once.
    2. If the difference between the maximum and minimum element is 1, then the number of distinct colors in the N object must be equal to the maximum element, because the minimum element is 1 less than the maximum element.
      • Now, assuming the frequency of the minimum element as X and the frequency of the maximum element as Y, then the answer is “Yes” if and only if X+1 ≤ A ≤ X+ Y/2 (observation-based).

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

  • Сначала отсортируйте массив в порядке возрастания.
  • Если разница между arr[N-1] и arr[0] больше 1, выведите « No ».
  • В противном случае, если arr[N-1] равно arr[0] , проверьте следующее:
    • Если arr[N-1] = N-1 или 2*arr[N-1] <= N , то выведите « Да ».
    • В противном случае выведите « Нет ».
  • В противном случае подсчитайте частоты элементов min и max и сохраните их в переменных, скажем, X и Y , а затем выполните следующие действия:
    • Если arr[N-1] больше X , а arr[N-1] меньше или равно X+Y/2 , выведите « Да ».
    • В противном случае выведите « Нет ».

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

Временная сложность: O (N * log (N))
Вспомогательное пространство: O(1)

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