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

Учитывая массив arr[] , состоящий из N положительных целых чисел, задача состоит в том, чтобы найти максимальное количество раз, когда каждый элемент массива может быть либо умножен на M , либо разделен на K.
Примечание. По крайней мере один элемент должен быть разделен на M и K соответственно в каждой операции.

Примеры:

Input: arr[] = {5, 2, 4}, M = 3, K = 2
Output: 3
Explanation:
One possible way to perform the operations is:

1. Multiply arr[1] and arr[2] by 3, and divide arr[3] by 2. The array modifies to {15, 6, 2}.
2. Multiply arr[1] and arr[3] by 3, divide arr[2] by 2. The array modifies to {45, 3, 6}.
3. Multiply arr[1] by 3 and arr[2] by 3 and divide arr[3] by 2. The array modifies to {135, 9, 3}.
4. No further operation is possible since no element is divisible by 2.

Therefore, the maximum number of operations possible is 3.

Input: arr[] = {3, 5, 7}
Output: 0

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

• Инициализируйте переменную, скажем, Count as 0, которая будет хранить количество в степени 2 в каждом элементе массива.
• Выполните итерацию в диапазоне [0, N-1], используя переменную i , и выполните следующие шаги:
  • Повторяйте до тех пор, пока arr[i] не станет делиться на 2, затем увеличьте Count на 1 и разделите arr[i] на 2 .
• После выполнения вышеуказанных шагов выведите значение Count в качестве ответа.

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

Временная сложность: O(N*log(M)), где M — максимальное значение массива.
Вспомогательное пространство: O(1)