Реализация Bit Stuffing и Bit Dstuffing

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

Примеры:

Input: N = 6, arr[] = {1, 1, 1, 1, 1, 1}
Output: 1111101
Explanation: During the traversal of the array, 5 consecutive 1’s are encountered after the 4th index of the given array. Hence, a zero bit has been inserted into the stuffed array after the 4th index 

Input: N = 6, arr[] = {1, 0, 1, 0, 1, 0}
Output: 101010

Подход: Идея состоит в том, чтобы проверить, состоит ли данный массив из 5 последовательных единиц . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте массив brr[], в котором хранится заполненный массив. Кроме того, создайте переменную count, которая поддерживает количество последовательных единиц.
• Пройдите в цикле while, используя переменную i в диапазоне [0, N), и выполните следующие задачи:
  • Если arr[i] равен 1 , проверьте следующие 4 бита, если они также установлены. Если да, то вставьте 0 бит после вставки всех 5 установленных битов в массив brr[] .
  • В противном случае вставьте значение arr[i] в массив brr[] .

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

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

Bit Dstuffing или Bit Unstuffing — это процесс отмены изменений в массиве, сделанных в процессе заполнения битами, т. е. удаление лишних нулевых битов после обнаружения 5 последовательных единиц .

Примеры:

Input: N = 7, arr[] = {1, 1, 1, 1, 1, 0, 1}
Output: 111111
Explanation: During the traversal of the array, 5 consecutive 1’s are encountered after the 4th index of the given array. Hence, the next 0 bit must be removed to de-stuffed array. 

Input: N = 6, arr[] = {1, 0, 1, 0, 1, 0}
Output: 101010

Подход: Эта проблема может быть решена аналогично проблеме вставки битов. Единственное необходимое изменение в рассмотренном выше подходе — всякий раз, когда встречаются 5 последовательных единиц , пропускать следующий бит в массиве arr[] вместо вставки нулевого бита в массиве brr[] .

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

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