Минимизируйте деление на 2, чтобы получить как минимум K четных чисел в заданном массиве.

Опубликовано: 25 Февраля, 2023

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

Примеры:

Input: arr = [2, 7, 4, 5, 6], K = 4
Output: 1
Explanation: Replace element at index 3 by its half.
So array becomes [2, 3, 4, 2, 6] which contains atleast K(i.e 4) even numbers.

Input: arr = [2, 7, 4, 5, 6], K = 6
Output: -1
Explanation: Array can contain atmost 5 even numbers after performing given operation.

Подход: Для решения задачи используйте следующую идею:

Any odd number can be written in the form of (4*x + 1) or (4*x + 3). For the odd numbers of form (4*x + 1) dividing once give an even number and for (4*x + 3) we need to half it twice to get an even number.

So based on this get count of even numbers and odd numbers of these two formats. Now to optimally half elements, first change odd numbers of type (4*x + 1) to an even number and then of the type (4*x + 3).

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

  • Объявите и инициализируйте переменные evenCount значением 0 , чтобы подсчитать количество четных целых чисел в исходном массиве.
  • Инициализируйте две другие переменные odd1 для хранения нечетных чисел типа (4*x + 1) .
  • Если evenCount больше или равен K , выведите 0 , так как массив уже содержит не менее K четных чисел.
  • В противном случае, если значение K больше, чем размер arr print -1 .
  • В противном случае сделайте следующее:
    • Если (K — evenCount) меньше или равно нечетному1 , верните это значение в качестве требуемого ответа.
    • В противном случае верните нечетный1 + (K – четныйКоличество – нечетный1)*2 в качестве требуемого ответа [поскольку (K-evenCount-нечетный1) нечетные элементы имеют тип (4*x + 3)].

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

Временная сложность: O(N)
Вспомогательное пространство: O(1), так как дополнительное пространство не требуется.

РЕКОМЕНДУЕМЫЕ СТАТЬИ