Задача. Добавить нули

Задача. Дан массив целых чисел. Необходимо продублировать каждое вхождение нуля, сдвигая оставшиеся элементы вправо.

Примечание. Элементы, превышающие длину исходного массива, не записываются. Обратите внимание, что все изменения должны быть выполнены в исходном массиве.

Примеры

1. [1,0,2,3,0,4,5,0]
   Output: [1,0,0,2,3,0,0,4]
2. [1,2,3]
   Output: [1,2,3]

Разбор

Приведем самое простое решение этой задачи, правда сложность алгоритма будет квадратичной. Попробуйте оптимизировать алгоритм самостоятельно.

Алгоритм

1. В 1м цикле пройдем по исходному массиву и будем искать 0.
2. Для каждого нулевого элемента запустим подцикл с конца массива до этого нулевого элемента, сдвигая элементы.
3. Добавим 2й нулевой элемент и дополнительно сдвинем наш счетчик, чтобы не обрабатывать добавленный нулевой элемент.

Реализация

Play-test

https://dotnetfiddle.net/sSVojk