Минимизируйте удаления, чтобы сумма массива делилась на 3

Учитывая массив arr[] размера N , задача состоит в том, чтобы вычислить минимальное количество элементов, которые нужно удалить из массива, чтобы сумма оставшихся элементов массива делилась на 3.

Примеры:

Input:  N = 3, arr[] = {1, 2, 3}
Output: 0
Explanation: 1+2+3 = 6 and it is already divisible by 3. 
So we need to remove 0 elements.

Input: N = 4, arr[] = {3, 6, 2, 2}
Output: 2
Explanation: 3+6+2+2 = 13. 
On removing last two elements, sum would become 9 which is divisible by 3. 
This is minimum number of elements to be removed.

Подход: Решение задачи основано на следующей математической идее:

• If the sum is already divisible by 3, no deletions required.
• If sum%3 = 1 then remove either 1 element (say x) such that x%3 = 1 or two elements (say x and y) such that (x%2 = y%2 = 2) because (2+2)%3 = 1.
• If sum%2 = 2, then either remove an element (say x) so that x%3 = 2 or remove two elements (say x, y) such that (x%2 = y%2 = 1) because (1+1)%3 = 2 

Выполните следующие шаги, чтобы решить эту проблему:

• Вычислите сумму всех элементов массива (скажем, sum ).
• Пройдите массив от i = 0 до N-1 :
  • Если элемент делится на 3, увеличьте количество элементов, делящихся на 3.
  • Точно так же сохраните количество элементов, у которых остаток = 1 и 2 при делении на 3.
• Теперь найдите минимальное количество удалений, требуемое из вышеупомянутых условий.

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

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