Задача с собеседования в Zendesk

Вам дано целое число money, обозначающее сумму денег (в долларах), которая у вас есть, и другое целое число children, обозначающее количество детей, между которыми вы должны распределить деньги.

Вы должны распределить деньги в соответствии со следующими правилами:
- Все деньги должны быть распределены;
- Каждый получает хотя бы 1 доллар;
- Никто не получает 4 доллара.

Верните максимальное количество детей, которые могут получить ровно 8 долларов, если вы распределите деньги согласно вышеуказанным правилам. Если распределить деньги невозможно, верните -1.

Пример 1:
Input: money = 20, children = 3
Output: 1
Explanation: Максимальное количество детей, которые получат 8 долларов, будет равно 1. Один из способов распределить деньги:
- 8 долларов первому ребёнку;
- 9 долларов второму ребёнку;
- 3 доллара третьему ребёнку.
Можно доказать, что не существует такого распределения, при котором количество детей, получающих 8 долларов, будет больше 1.

Пример 2:
Input: money = 16, children = 2
Output: 2
Explanation: Каждому ребёнку можно дать по 8 долларов.

Ограничения:
1 <= money <= 200
2 <= children <= 30

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Итак, нам нужно определить максимальное кол-во детей, которые могут получить ровно 8 долларов.
Сначала раздадим каждому по 1 обязательному доллару, чтобы гарантировать соблюдение правила. Оставшаяся после распределения сумма не должна быть отрицательной, иначе это означает, что детей было больше, чем долларов, и мы не смогли бы дать каждому даже по 1 доллару.
Оставшиеся деньги мы можем распределить дополнительно и раздать максимально возможному кол-ву детей ещё по 7 долларов => кол-во детей, которые могут получить ровно 8 долларов равно: remaining_money // 7.

Рассмотрим три случая:
1. Все дети получат по 8 долларов, если результат целочисленного деления будет равен количеству детей с остатком равным 0.

2. Если можем дать дополнительные 7 долларов всем, кроме одного, и при этом остаток денег равняется 3: мы вынуждены забрать доллар у ребёнка с 8 долларами и отдать его ребёнку с 4 долларами. Таким образом, у нас гарантированно будет 2 ребёнка, которые не смогут получить 8 долларов, не нарушая правила (значит, кол-во тех, кто сможет: children - 2).

3. Базовый случай: у нас есть два ограничения - кол-во денег (remaining_money // 7) и кол-во детей, которые могут получить 8 долларов с учётом того, что необходимо отдать остаток после распределения одному ребёнку (children - 1).
Ограничения должны быть соблюдены одновременно, поэтому мы выбираем самое строгое из них. То есть берём минимум, который и будет нашим максимально возможным кол-вом детей.

Сложность
O(1) - по времени
O(1) - по памяти

Код
class Solution:
def distMoney(self, money: int, children: int) -> int:
remaining_money = money - children

if remaining_money < 0:
return -1

if (remaining_money // 7 == children and remaining_money % 7 == 0):
return children

if (remaining_money // 7 == children - 1 and remaining_money % 7 == 3):
return children - 2

return min(children - 1, remaining_money // 7)

@algoses