El relleno de bits es un proceso de inserción de un bit adicional como 0 , una vez que la secuencia de cuadros encontró 5 1 consecutivos . Dada una array , arr[] de tamaño N que consta de 0 y 1, la tarea es devolver una array después del relleno de bits.
Ejemplos:
Entrada: N = 6, arr[] = {1, 1, 1, 1, 1, 1}
Salida: 1111101
Explicación: Durante el recorrido de la array, se encuentran 5 1 consecutivos después del 4º índice de la array dada. Por lo tanto, se ha insertado un bit cero en la array rellena después del cuarto índiceEntrada: N = 6, arr[] = {1, 0, 1, 0, 1, 0}
Salida: 101010
Enfoque: la idea es verificar si la array dada consta de 5 1 consecutivos . Siga los pasos a continuación para resolver el problema:
- Inicialice la array brr[] que almacena la array rellena. Además, cree una cuenta variable que mantenga la cuenta de los 1 consecutivos.
- Atraviese un ciclo while usando una variable i en el rango [0, N) y realice las siguientes tareas:
- Si arr[i] es 1 , compruebe los siguientes 4 bits si también son bits establecidos. Si es así, inserte un bit 0 después de insertar los 5 bits establecidos en la array brr[] .
- De lo contrario, inserte el valor de arr[i] en la array brr[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function for bit stuffing
void bitStuffing(int N, int arr[])
{
// Stores the stuffed array
int brr[30];
// Variables to traverse arrays
int i, j, k;
i = 0;
j = 0;
// Stores the count of consecutive ones
int count = 1;
// Loop to traverse in the range [0, N)
while (i < N)
{
// If the current bit is a set bit
if (arr[i] == 1)
{
// Insert into array brr[]
brr[j] = arr[i];
// Loop to check for
// next 5 bits
for(k = i + 1; arr[k] == 1 && k < N && count < 5;
k++)
{
j++;
brr[j] = arr[k];
count++;
// If 5 consecutive set bits
// are found insert a 0 bit
if (count == 5)
{
j++;
brr[j] = 0;
}
i = k;
}
}
// Otherwise insert arr[i] into
// the array brr[]
else
{
brr[j] = arr[i];
}
i++;
j++;
}
// Print Answer
for(i = 0; i < j; i++)
cout << brr[i];
}
// Driver code
int main()
{
int N = 6;
int arr[] = { 1, 1, 1, 1, 1, 1 };
bitStuffing(N, arr);;
return 0;
}
// This code is contributed by target_2
C
// C program for the above approach
#include <stdio.h>
#include <string.h>
// Function for bit stuffing
void bitStuffing(int N, int arr[])
{
// Stores the stuffed array
int brr[30];
// Variables to traverse arrays
int i, j, k;
i = 0;
j = 0;
// Stores the count of consecutive ones
int count = 1;
// Loop to traverse in the range [0, N)
while (i < N) {
// If the current bit is a set bit
if (arr[i] == 1) {
// Insert into array brr[]
brr[j] = arr[i];
// Loop to check for
// next 5 bits
for (k = i + 1;
arr[k] == 1
&& k < N
&& count < 5;
k++) {
j++;
brr[j] = arr[k];
count++;
// If 5 consecutive set bits
// are found insert a 0 bit
if (count == 5) {
j++;
brr[j] = 0;
}
i = k;
}
}
// Otherwise insert arr[i] into
// the array brr[]
else {
brr[j] = arr[i];
}
i++;
j++;
}
// Print Answer
for (i = 0; i < j; i++)
printf("%d", brr[i]);
}
// Driver Code
int main()
{
int N = 6;
int arr[] = { 1, 1, 1, 1, 1, 1 };
bitStuffing(N, arr);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function for bit stuffing
static void bitStuffing(int N, int arr[])
{
// Stores the stuffed array
int []brr = new int[30];
// Variables to traverse arrays
int i, j, k;
i = 0;
j = 0;
// Stores the count of consecutive ones
int count = 1;
// Loop to traverse in the range [0, N)
while (i < N) {
// If the current bit is a set bit
if (arr[i] == 1) {
// Insert into array brr[]
brr[j] = arr[i];
// Loop to check for
// next 5 bits
for (k = i + 1; k < N &&
arr[k] == 1
&& count < 5;
k++) {
j++;
brr[j] = arr[k];
count++;
// If 5 consecutive set bits
// are found insert a 0 bit
if (count == 5) {
j++;
brr[j] = 0;
}
i = k;
}
}
// Otherwise insert arr[i] into
// the array brr[]
else {
brr[j] = arr[i];
}
i++;
j++;
}
// Print Answer
for (i = 0; i < j; i++)
System.out.printf("%d", brr[i]);
}
// Driver Code
public static void main(String[] args)
{
int N = 6;
int arr[] = { 1, 1, 1, 1, 1, 1 };
bitStuffing(N, arr);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach # Function for bit stuffing def bitStuffing(N, arr): # Stores the stuffed array brr = [0 for _ in range(30)] # Variables to traverse arrays k = 0 i = 0 j = 0 # Stores the count of consecutive ones count = 1 # Loop to traverse in the range [0, N) while (i < N): # If the current bit is a set bit if (arr[i] == 1): # Insert into array brr[] brr[j] = arr[i] # Loop to check for # next 5 bits k = i + 1 while True: if not (k < N and arr[k] == 1 and count < 5): break j += 1 brr[j] = arr[k] count += 1 # If 5 consecutive set bits # are found insert a 0 bit if (count == 5): j += 1 brr[j] = 0 i = k k += 1 # Otherwise insert arr[i] into # the array brr[] else: brr[j] = arr[i] i += 1 j += 1 # Print Answer for i in range(0, j): print(brr[i], end = "") # Driver Code if __name__ == "__main__": N = 6 arr = [ 1, 1, 1, 1, 1, 1 ] bitStuffing(N, arr) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
class GFG{
// Function for bit stuffing
static void bitStuffing(int N, int[] arr)
{
// Stores the stuffed array
int[] brr = new int[30];
// Variables to traverse arrays
int i, j, k;
i = 0;
j = 0;
// Stores the count of consecutive ones
int count = 1;
// Loop to traverse in the range [0, N)
while (i < N)
{
// If the current bit is a set bit
if (arr[i] == 1)
{
// Insert into array brr[]
brr[j] = arr[i];
// Loop to check for
// next 5 bits
k = i + 1;
while (k < N && arr[k] == 1 && count < 5)
{
j++;
brr[j] = arr[k];
count++;
// If 5 consecutive set bits
// are found insert a 0 bit
if (count == 5)
{
j++;
brr[j] = 0;
}
i = k;
k++;
}
}
// Otherwise insert arr[i] into
// the array brr[]
else
{
brr[j] = arr[i];
}
i++;
j++;
}
// Print Answer
for(i = 0; i < j; i++)
Console.Write(brr[i]);
}
// Driver Code
public static void Main()
{
int N = 6;
int[] arr = { 1, 1, 1, 1, 1, 1 };
bitStuffing(N, arr);
}
}
// This code is contributed by ukasp
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function for bit stuffing
function bitStuffing(N, arr)
{
// Stores the stuffed array
let brr = new Array(30);
// Variables to traverse arrays
let i, j, k;
i = 0;
j = 0;
// Stores the count of consecutive ones
let count = 1;
// Loop to traverse in the range [0, N)
while (i < N) {
// If the current bit is a set bit
if (arr[i] == 1) {
// Insert into array brr[]
brr[j] = arr[i];
// Loop to check for
// next 5 bits
for (k = i + 1;
arr[k] == 1
&& k < N
&& count < 5;
k++) {
j++;
brr[j] = arr[k];
count++;
// If 5 consecutive set bits
// are found insert a 0 bit
if (count == 5) {
j++;
brr[j] = 0;
}
i = k;
}
}
// Otherwise insert arr[i] into
// the array brr[]
else {
brr[j] = arr[i];
}
i++;
j++;
}
// Print Answer
for (i = 0; i < j; i++)
document.write(brr[i] + " ");
}
// Driver Code
let N = 6;
let arr = [1, 1, 1, 1, 1, 1];
bitStuffing(N, arr);
// This code is contributed by Potta Lokesh
</script>
Producción
1111101
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Bit Destuffing o Bit Unstuffing es un proceso de deshacer los cambios en la array realizados durante el proceso de relleno de bits , es decir, eliminar el bit 0 adicional después de encontrar 5 1 consecutivos .
Ejemplos:
Entrada: N = 7, arr[] = {1, 1, 1, 1, 1, 0, 1}
Salida: 111111
Explicación: Durante el recorrido de la array, se encuentran 5 1 consecutivos después del 4to índice de la array dada . Por lo tanto, el siguiente bit 0 debe eliminarse para eliminar el relleno.Entrada: N = 6, arr[] = {1, 0, 1, 0, 1, 0}
Salida: 101010
Enfoque: Este problema se puede resolver de manera similar al problema de relleno de bits . El único cambio requerido en el enfoque discutido anteriormente es siempre que se encuentren 5 1 consecutivos , omita el siguiente bit en la array arr[] en lugar de insertar un bit 0 en la array brr[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function for bit de-stuffing
void bitDestuffing(int N, int arr[])
{
// Stores the de-stuffed array
int brr[30];
// Variables to traverse the arrays
int i, j, k;
i = 0;
j = 0;
// Stores the count of consecutive ones
int count = 1;
// Loop to traverse in the range [0, N)
while (i < N) {
// If the current bit is a set bit
if (arr[i] == 1) {
// Insert into array brr[]
brr[j] = arr[i];
// Loop to check for the next 5 bits
for (k = i + 1; arr[k] == 1 && k < N && count < 5; k++) {
j++;
brr[j] = arr[k];
count++;
// If 5 consecutive set bits are found skip the next bit in arr[]
if (count == 5) {
k++;
}
i = k;
}
}
// Otherwise insert arr[i] into the array brr
else {
brr[j] = arr[i];
}
i++;
j++;
}
// Print Answer
for (i = 0; i < j; i++)
cout<< brr[i];
}
// Driver Code
int main()
{
int N = 7;
int arr[] = { 1, 1, 1, 1, 1, 0, 1 };
bitDestuffing(N, arr);
return 0;
}
// This code is contributed by ajaymakvana
C
// C program for the above approach
#include <stdio.h>
#include <string.h>
// Function for bit de-stuffing
void bitDestuffing(int N, int arr[])
{
// Stores the de-stuffed array
int brr[30];
// Variables to traverse the arrays
int i, j, k;
i = 0;
j = 0;
// Stores the count of consecutive ones
int count = 1;
// Loop to traverse in the range [0, N)
while (i < N) {
// If the current bit is a set bit
if (arr[i] == 1) {
// Insert into array brr[]
brr[j] = arr[i];
// Loop to check for
// the next 5 bits
for (k = i + 1;
arr[k] == 1
&& k < N
&& count < 5;
k++) {
j++;
brr[j] = arr[k];
count++;
// If 5 consecutive set
// bits are found skip the
// next bit in arr[]
if (count == 5) {
k++;
}
i = k;
}
}
// Otherwise insert arr[i] into
// the array brr
else {
brr[j] = arr[i];
}
i++;
j++;
}
// Print Answer
for (i = 0; i < j; i++)
printf("%d", brr[i]);
}
// Driver Code
int main()
{
int N = 7;
int arr[] = { 1, 1, 1, 1, 1, 0, 1 };
bitDestuffing(N, arr);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function for bit de-stuffing
static void bitDestuffing(int N, int arr[])
{
// Stores the de-stuffed array
int []brr = new int[30];
// Variables to traverse the arrays
int i, j, k;
i = 0;
j = 0;
// Stores the count of consecutive ones
int count = 1;
// Loop to traverse in the range [0, N)
while (i < N) {
// If the current bit is a set bit
if (arr[i] == 1) {
// Insert into array brr[]
brr[j] = arr[i];
// Loop to check for
// the next 5 bits
for (k = i + 1; k<N &&
arr[k] == 1
&& count < 5;
k++) {
j++;
brr[j] = arr[k];
count++;
// If 5 consecutive set
// bits are found skip the
// next bit in arr[]
if (count == 5) {
k++;
}
i = k;
}
}
// Otherwise insert arr[i] into
// the array brr
else {
brr[j] = arr[i];
}
i++;
j++;
}
// Print Answer
for (i = 0; i < j; i++)
System.out.printf("%d", brr[i]);
}
// Driver Code
public static void main(String[] args)
{
int N = 7;
int arr[] = { 1, 1, 1, 1, 1, 0, 1 };
bitDestuffing(N, arr);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python program for the above approach # Function for bit de-stuffing def bitDestuffing(N, arr): # Stores the de-stuffed array brr = [0 for i in range(30)]; # Variables to traverse the arrays k = 0; i = 0; j = 0; # Stores the count of consecutive ones count = 1; # Loop to traverse in the range [0, N) while (i < N): # If the current bit is a set bit if (arr[i] == 1): # Insert into array brr brr[j] = arr[i]; # Loop to check for # the next 5 bits for k in range(i + 1, k < N and arr[k] == 1 and count < 5,1): j += 1; brr[j] = arr[k]; count += 1; # If 5 consecutive set # bits are found skip the # next bit in arr if (count == 5): k += 1; i = k; # Otherwise insert arr[i] into # the array brr else: brr[j] = arr[i]; i += 1; j += 1; # Print Answer for i in range(0, j): print(brr[i],end=""); # Driver Code if __name__ == '__main__': N = 7; arr = [1, 1, 1, 1, 1, 0, 1]; bitDestuffing(N, arr); # This code contributed by shikhasingrajput
C#
// C# program for the above approach
using System;
class GFG{
// Function for bit de-stuffing
static void bitDestuffing(int N, int[] arr)
{
// Stores the de-stuffed array
int []brr = new int[30];
// Variables to traverse the arrays
int i, j, k;
i = 0;
j = 0;
// Stores the count of consecutive ones
int count = 1;
// Loop to traverse in the range [0, N)
while (i < N) {
// If the current bit is a set bit
if (arr[i] == 1) {
// Insert into array brr[]
brr[j] = arr[i];
// Loop to check for
// the next 5 bits
for (k = i + 1; k<N &&
arr[k] == 1
&& count < 5;
k++) {
j++;
brr[j] = arr[k];
count++;
// If 5 consecutive set
// bits are found skip the
// next bit in arr[]
if (count == 5) {
k++;
}
i = k;
}
}
// Otherwise insert arr[i] into
// the array brr
else {
brr[j] = arr[i];
}
i++;
j++;
}
// Print Answer
for (i = 0; i < j; i++)
Console.Write(brr[i]);
}
// Driver Code
public static void Main()
{
int N = 7;
int[] arr = { 1, 1, 1, 1, 1, 0, 1 };
bitDestuffing(N, arr);
}
}
// This code is contributed by gfgking
Javascript
<script>
// javascript program for the above approach// Function for bit de-stuffing
function bitDestuffing(N , arr)
{
// Stores the de-stuffed array
var brr = Array.from({length: 30}, (_, i) => 0);
// Variables to traverse the arrays
var i, j, k;
i = 0;
j = 0;
// Stores the count of consecutive ones
var count = 1;
// Loop to traverse in the range [0, N)
while (i < N) {
// If the current bit is a set bit
if (arr[i] == 1) {
// Insert into array brr
brr[j] = arr[i];
// Loop to check for
// the next 5 bits
for (k = i + 1; k<N &&
arr[k] == 1
&& count < 5;
k++) {
j++;
brr[j] = arr[k];
count++;
// If 5 consecutive set
// bits are found skip the
// next bit in arr
if (count == 5) {
k++;
}
i = k;
}
}
// Otherwise insert arr[i] into
// the array brr
else {
brr[j] = arr[i];
}
i++;
j++;
}
// Print Answer
for (i = 0; i < j; i++)
document.write(brr[i]);
}
// Driver Code
var N = 7;
var arr = [ 1, 1, 1, 1, 1, 0, 1 ];
bitDestuffing(N, arr);
// This code is contributed by 29AjayKumar
</script>
Producción
111111
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por bunny09262002 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA