Свести к минимуму операции по преобразованию элементов массива в 0

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

Дан массив nums[] длины N , содержащий неотрицательные целые числа, задача состоит в том, чтобы преобразовать все элементы от индекса 0 до N-2 до нуля, после выполнения приведенных ниже операций минимальное количество раз.

  • В одной операции выберите два индекса i и j такие, что i < j и все элементы между i и j должны быть ненулевыми , затем установите nums[i] = nums[i] – 1 и nums[j] = nums[ я] + 1.

Примеры:

Input: N = 5, nums[] = [0, 2, 0, 2, 0]
Output: 5
Explanation: We need to do 5 above given operation 
to complete the task, and the operations are:

  • Select j = 3, k = 4 nums[] becomes: [0, 2, 0, 1, 1]
  • Select j = 1, k = 2 nums[] becomes: [0, 1, 1, 1, 1]
  • Select j = 1, k = 4 nums[] becomes: [0, 0, 1, 1, 2]
  • Select j = 2, k = 4 nums[] becomes: [0, 0, 0, 1, 3]
  • Select j = 3, k = 4 nums[] becomes: [0, 0, 0, 0, 4]

Input: N = 3, nums[] = [2, 0, 0]
Output: 3
Explanation: We need to do 3 above given operation 
to complete the task, and the operations are:

  • Select j = 0, k = 1 nums[] becomes: [1, 1, 0]
  • Select j = 0, k = 2 nums[] becomes: [0, 1, 1]
  • Select j = 1, k = 2 nums[] becomes: [0, 0, 2]

Подход: Задача может быть решена на основе следующей идеи:

  • The possible way to convert all elements from 0 to N-2 to 0 is by reducing each element from the left by 1 and adding 1 each time to the last element, until leftmost element become zero and then moving to the next index. So the number of operations will be the sum of elements from 0 to N-2.
  • But if there is a 0 present in between then first we have to convert that 0 into a positive number, so that we can perform the operation for the elements present in the left of that 0. 
  • To convert a 0 to a positive element, 1 operation will take place, so our final answer will be the sum of elements from 0 to N-2 and the number of zeros present after the first positive element. 

Следуйте шагам, приведенным ниже, чтобы реализовать подход:

  • Сначала пройдитесь по массиву, пока не получите первый ненулевой элемент.
    • После этого, если элемент не равен нулю , обновите ans += nums[i]
    • В противном случае, если элемент равен нулю, обновите += 1.
  • Пройдите по заданному массиву до N-2 и вычислите требуемый ответ, как указано выше.
  • Вернуть рассчитанный ответ.

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

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

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