Количество расположений RGB-шаров без дубликатов в наборе

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

Даны R красных шаров, G зеленых шаров, B синих шаров. В наборе может быть 1 , 2 или 3 мяча. Кроме того, в наборе могут быть все шары одного цвета или все шары разных цветов. Все остальные возможные наборы не считаются действительными. Задача состоит в том, чтобы вычислить минимально возможные наборы, необходимые для размещения всех шаров.

Примеры:

Input: R = 4, G = 2, B = 4
Output: 4
Explanation: There can be 4 sets which satisfies all condition mentioned above {R, R, R}, {B, B, B}, {G, R}, {G, B}.
Therefore, the answer is 4. 

Input: R = 1, G = 7, B = 1
Output: 3
Explanation: There are 3 valid sets {R, G, B}, {G, G, G}, {G, G, G}

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

  • Постановка проблемы может быть решена путем тщательного анализа случая.
  • Без ограничения общности предположим, что R<=G<=B.
  • Таким образом, будет сформировано не менее R наборов. Вычтите R из G и B. Во всех наборах, сформированных на этом шаге, будут разные шары.
  • Остальные шары будут 0, G-R, B-R . Для остальных шаров сформируйте наборы из таких же шаров.
  • После вышеуказанного шага оставшиеся шары будут 0, (G – R)%3, (B – R)%3.
  • Теперь может быть 3 случая:
  • 2-й член равен 0, 3-й член равен нулю. Дополнительный набор не потребуется.
  • (2-й член равен 1, 3-й член равен 1) или (2-й член равен 0, а 3-й член равен 2 или наоборот). Потребуется 1 дополнительный комплект.
  • Во всех остальных случаях потребуется еще 2 комплекта.
  • Внимательно проверьте все приведенные выше условия и распечатайте ответ.

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

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

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