Максимальное количество групп из заданных 0, 1 и 2 с суммой, кратной 3

Даны три целых числа C0, C1 и C2 частоты нулей, единиц и двоек в группе S . Задача состоит в том, чтобы найти максимальное количество групп, сумма которых делится на 3 , условие состоит в том, что сумма (S) делится на 3, а объединение всех групп должно быть равно S

Примеры:

Input: C0 = 2, C1 = 4, C2 = 1
Output: 4
Explanation: it can divide the group S = {0, 0, 1, 1, 1, 1, 2} into four groups {0}, {0}, {1, 1, 1}, {1, 2}. It can be proven that 4 is the maximum possible answer.

Input: C0 = 250, C1 = 0, C2 = 0
Output: 250

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

• Инициализируйте переменную maxAns , скажем, 0, чтобы сохранить максимальное количество групп.
• Добавьте C0 к maxAns , потому что каждый {0} может быть группой, сумма которой делится на 3 .
• Инициализируйте переменную k , скажем min(C1, C2) , и добавьте ее в maxAns, потому что можно создать как минимум группу k , {1, 2} .
• Добавьте abs(C1-C2)/3 к maxAns , это будет вклад оставшихся 1s или 2s .
• Вернуть максАнс.

Ниже приведена реализация описанного выше подхода.

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