Проверьте, можно ли опустошить все 3 мешка с конфетами, удалив 2 конфеты из любого мешка и 1 из двух других несколько раз.

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

Даны 3 целых числа a, b и c , обозначающие количество конфет в трех пакетах. Вам нужно выяснить, можем ли мы опустошить все мешки, выполнив определенную операцию, где в каждой операции вы можете съесть 2 конфеты из одного мешка и по 1 конфете из двух других мешков. Нельзя пропускать ни одного мешка , т.е. из каждого мешка нужно съедать 1 или 2 конфеты за каждую операцию. Верните true, если возможно, иначе верните false.

Примеры:

Input: 4, 2, 2
Output: true
Explanation: 
Operation 1: you can eat 2 candies from bag1 and 1 from bag2 and bag3 each.
Candies left after operation 1
bag1 = 2, bag2 = 1, bag3 = 1
Operation 2: you can eat 2 candies from bag1 and 1 from each bag2 and bag3 each
Candies left after operation 2
bag1 = 0, bag2 = 0, bag3 = 0
Hence it is possible to empty all the bags

Input: 3, 4, 2
Output: false

Наивный подход: повторяйте переменные до тех пор, пока все три не станут равными 0. На каждой итерации уменьшайте максимальный элемент на 2, а оставшиеся переменные на 1.

Временная сложность: O(N), где N — значение максимальной переменной a, b и c .

Эффективный подход : Данную проблему можно решить с помощью эффективного подхода, сделав следующие наблюдения:

  • В каждой операции мы будем выбирать 1+2+1=4 конфеты, поэтому сумма всех конфет в мешке1, мешке2 и мешке3 должна делиться на 4 .
  • Количество операций , необходимых для опорожнения всех мешков, будет (сумма всех конфет)/4 .
  • Мы должны взять 1 или 2 конфеты из мешка при любой операции, следовательно, минимальное количество конфет, присутствующих в 3 мешках, должно быть больше или равно количеству операций.

Временная сложность: O(1)
Космическая сложность: O(1)

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