Минимум элементов, которые нужно вставить, чтобы ни один подмассив не имел сумму 0
Дан массив 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)