Максимальное количество 001 и 110, которые могут быть сформированы с помощью M 0s и N 1s

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

Даны два целых числа N (обозначающее число «1») и M (обозначающее число «0»). Задача состоит в том, чтобы максимизировать количество шаблонов «001» или «110» , которые можно составить, используя заданное количество символов.

Примеры:

Input:  N = 5, M = 5
Output: 3
Explanation: Possible patterns are {001, 110, 001}

Input: N = 7, M = 10
Output: 5

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

  • Если N/2 >= M , то будет сформирован только 001 паттерн и максимальное количество паттернов в таком случае будет M .
  • Если M/2 >= N , то будет сформировано только 110 паттернов и максимальное количество паттернов в таком случае будет N.
  • В противном случае, если abs(NM) < 2*min(N, M) , в этом случае будет выведено (N+M)/3 .
  • Распечатайте результат в соответствии с указанными выше условиями.

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

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

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