Минимальное деление на 2 операции, необходимое для того, чтобы сделать GCD нечетным для данного массива

Учитывая массив arr[] из N положительных целых чисел, задача состоит в том, чтобы найти минимальное количество операций, необходимых для того, чтобы сделать НОД элемента массива нечетным, чтобы в каждой операции элемент массива можно было разделить на 2 .

Примеры:

Input: arr[] = {4, 6}
Output: 1
Explanation:
Below are the operations performed:
Operation 1: Divide the array element arr[0](= 4) by 2 modifies the array to {2, 6}.
Operation 2: Divide the array element arr[0](= 2) by 2 modifies the array to {1, 6}.
After the above operations, the GCD of the array elements is 1 which is odd. Therefore, the minimum number of operations required is 2.

Input: arr[] = {2, 4, 1}
Output: 0

Подход: данная проблема может быть решена на основе наблюдения путем нахождения количества степеней 2 для каждого элемента массива, а минимальная мощность 2 (скажем, C ) даст минимальные операции, потому что после деления этого элемента на 2 ^C элемент становится нечетным, и это приводит к тому, что НОД массива является нечетным.

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

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