Подсчитайте комбинацию 4 и/или 5, необходимую для того, чтобы сделать каждый элемент массива равным 0.

Дан массив arr[] , состоящий из N положительных целых чисел, задача состоит в том, чтобы проверить, может ли каждый элемент массива быть представлен в терминах чисел 4 и 5 . Если это возможно, то выведите общее количество 4 и 5 , необходимое для каждого элемента массива. В противном случае выведите -1.

Примеры:

Input: arr[] = {12, 11, 9}
Output: 3 -1 2
Explanation: 

1. arr[0]( =12): Print 3 as it can be represented by using 3 fours i.e. 4 + 4 + 4 = 12.
2. arr[1](= 11): Print -1 as it cannot be represented by any combination of 4 and 5.
3. arr[2](= 9): Print 2 as it can be represented by using one 4 and one 5 i.e. 4 + 5 = 9.

Input: arr[] = {7, 15, 17, 22}
Output: -1 3 4 5

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

• Инициализируйте вектор, скажем , ans, как {-1} , где ans[i] хранит ответ на возможный ответ для значения arr[i] массива arr[].
• Переберите диапазон [0, N-1], используя переменную i , и выполните следующие шаги:
  • Если arr[i] меньше 4, то продолжаем.
  • Инициализируйте две переменные, скажем, sum как INT_MAX , чтобы сохранить количество чисел 4 и 5 , необходимых для формирования arr[i] , и cnt как 0 , чтобы сохранить счет текущего фактора 4.
  • Переберите диапазон [0, arr[i]] , используя переменную j , и выполните следующие шаги:
    • Если (arr[i] – j) делится на 5, то установите значение суммы равным минимуму суммы и (cnt + (arr[i] – j)/5).
    • Увеличьте значение cnt на 1 и j на 4 .
  • Если сумма не равна INT_MAX, то установите значение ans[i] в векторе ans как сумму.
• Наконец, после выполнения вышеуказанных шагов выведите значения в векторе ans.

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

Временная сложность: O(N*M), где M — максимальный элемент массива arr[].
Вспомогательное пространство: O(N)

Примечание. Приведенный выше подход может быть дополнительно оптимизирован с точки зрения пространственной сложности, поскольку сохранение результата перед печатью в описанном выше подходе является необязательным. После этого пространственная сложность будет оптимизирована до O(1).