Минимум элементов, которые нужно вставить, чтобы ни один подмассив не имел сумму 0

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

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

Примеры:

Input: N = 3, arr[] = {1, -1, 1}
Output: 2
Explanation: As in the array the sum of first two element is 0 that is 1+(-1) =  0. 
To avoid this, insert an element. Insert 10 at position 2. 
The array become {1, 10, -1, 1}. 
Now the sum of last 2 element is 0. To avoid this insert an element. 
Insert 10 at position 4. Array become {1, 10, -1, 10, 1}. 
Now, no subarray have sum 0. 
So we have to insert minimum 2 integers in the array.

Input: N = 4, arr[] = {-2, 1, 2, 3}
Output: 
Explanation: No array is there whose sum is 0. 
So no need to insert element.

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

Наблюдения:

  • If we get any subarray with sum 0. Then insert an element just 1 place before the position where you got sum 0. So that sum will not remain 0 and start doing sum again.
  • Do the same process till the end and print how many times you have inserted element.

Следуйте инструкциям, чтобы решить проблему:

  • Возьмите unordered_map для хранения сведений о сумме, чтобы узнать, есть ли подмассив с суммой 0.
  • Возьмите переменную ans и инициализируйте ее значением 0, чтобы сохранить минимальное количество вставляемых элементов.
  • Пройдитесь по массиву и добавьте каждый элемент в массив, а также обратите внимание на детали суммы на карте.
  • Если вы получили сумму 0 (что можно найти, проверив, присутствует ли сумма уже на карте):
    • Затем увеличьте ответ на 1 и измените сумму на текущее значение элемента, потому что вы позаботились о предыдущих элементах, а также удалили записи суммы с карты.
    • Повторяйте этот шаг каждый раз, когда есть подмассив с суммой 0 .
  • В последнем ответе .

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

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

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