Минимизируйте умножение на позицию, чтобы продукт массива делился на 2^K

Дан массив nums [] размера N , содержащий положительные целые числа и натуральное число K , задача состоит в том, чтобы найти минимальное количество операций, при котором произведение массива делится на 2 ^K , где в каждой операции nums[i] умножается на его позиция (т.е. i+1 ).

Примечание. Верните -1, если невозможно сделать произведение массива кратным 2 ^K .

Примеры:

Input: N = 2, K = 2, nums[] = { 3, 2 }
Output: 1
Explanation: The product of nums is 6 which is not divisible by 2² = 4. Make nums[2] = 2 * 2 = 4, then the product of the array becomes 12 which is divisible by 2².

Input: N = 3, K = 3, nums[] = { 2, 1, 3 }
Output: -1
Explanation: The product of nums is 6 which is not divisible by 2³ = 8. If we make nums[2] = 1 * 2 = 2, then also the product will become 12 which is not divisible by 2³.

Подход: это можно решить, используя следующую идею:

Count the number of times each element of array and index i is divisible by 2 and store the count of each in a variable and check whether count of two is more than K or not.

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

• Инициализируйте переменную (скажем, curr = 0 ).
• Пройдите массив nums[] и сохраните количество двоек в факторизации каждого элемента в переменной curr и количество двоек в индексе i и сохраните их в векторе v .
• Если переменная curr больше или равна K , верните 0.
• Отсортируйте вектор v в порядке возрастания.
• Инициализируйте res = 0 , чтобы подсчитать количество необходимых операций.
  • Пока значение curr меньше K , а v не пусто, оптимальным образом увеличьте curr с помощью v.back() , т.е. максимальное количество двоек в индексах [1, n], вытолкните обратно из v и увеличьте res на 1.
• Когда обход завершится, проверьте, меньше ли текущее значение, чем K , затем верните -1 .
• В противном случае верните res как необходимое количество операций.

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

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