Zero Insert After K Times One

 Zero Insert After K Times One 

PROBLEM STATEMENT :

Given a bitstream of length N consisting of 0s and 1s, insert 0 after 1 has appeared K times consecutively. 

Input Format: 

The first line contains N and K separated by a space. 

The second line contains the bitstream with 1s and 0s with each value separated by a space. 

Output Format: 

In the first line, the bitstream with the 0 inserted after 1s has appeared K times with each value separated by a space. 

Boundary Conditions: 

1 <= K <= 1000 

2 <= N <= 1000 

Example Input/Output 1: 
Input: () 
12 2 
1 0 1 1 0 1 1 0 1 1 1 1
Output: 
1 0 1 1 0 0 1 1 0 0 1 1 0 1 1 0 

---

SOLUTION :

C (Programming Language)

      
#include<stdio.h>
#include<stdlib.h>

int main()
{
    int n,k,cnt=0,i,j,a[2002];
    scanf("%d%d",&n,&k);
    for(i=0;i<n;++i) 
    {
        scanf("%d",&a[i]);
    }
    //Count of 1 in first step
    for(i=0;i<k;++i)
    {
        if(a[i]==1) cnt++;
    }
    for(i=k;i<=n;++i)
    {
        if(cnt==k) 
        {
            //insert 1 
            for(j=n-1;j>=i;--j)
            {
                a[j+1]=a[j];
            }
            a[i]=0;
            n+=1; //size increased by 1
        }
        //Change cnt by checking the corner cases
        if(a[i]==1) cnt++;
        if(a[i-k]==1) cnt--;
    }
    for(i=0;i<n;++i)
    {
        printf("%d ",a[i]);
    }
}
 

C++ (CPP)

       
#include <bits/stdc++.h>
 
using namespace std;

int main(int argc, char** argv)
{
    int n,k,i,cnt=0;
    cin>>n>>k;
    vector<int> v;
    for(i=0;i<n;++i)
    {
        int num;
        cin>>num;
        v.push_back(num);
    }
    for(i=0;i<k;++i)
    {
        if(v[i]==1) cnt++;
    }
    for(i=k;i<=n;++i)
    {
        if(cnt==k)
        {
            v.insert(v.begin()+i,0);
            n+=1;
        }
        if(i<n&&v[i]==1) cnt++;
        if(v[i-k]==1) cnt--;
    }
    for(i=0;i<n;++i)
    {
        cout<<v[i]<<" ";
    }
}
 

JAVA

       
import java.util.*;
public class Hello {

    public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt(),k=sc.nextInt(),i,cnt=0;
		ArrayList<Integer> a=new ArrayList<Integer>(2002);
		for(i=0;i<n;++i)
		{
		    a.add(sc.nextInt());
		}
		for(i=0;i<k;++i)
		{
		    if(a.get(i)==1) cnt++;
		}
		for(i=k;i<=n;++i)
		{
		    if(cnt==k)
		    {
		        a.add(i,0);
		        n+=1;
		    }
		    if(i<n&&a.get(i)==1) cnt+=1;
		    if(a.get(i-k)==1) cnt-=1;
		}
		for(i=0;i<n;++i)
		{
		    System.out.print(a.get(i)+" ");
		}
	}
}
 

PYTHON

       
n,k=map(int,input().split())
l=list(map(int,input().split()))
i=0
while i<=len(l):
    if l[i-k:i]==([1]*k):
        l.insert(i,0)
    i+=1
print(*l)
 

Never Stop Learning !!