CareerCup

Sorry for incomplete question, you need to give the number of swaps required.

* parse the string from right to left
* when doing so keep track of the number of zeros
* when you encounter a 1, add the current count of zeros to total counts

At the end of the loop, total counts will have the minimum number of swaps needed

The most efficient way is only when we are swapping only 0<->1 (not 0<->0 and not 1<->1)
So we have to count "1" on the left side of each "0".

public int countMoves(String stext) {
		int oneCount = 0;
		int result = 0;
		char[] ch = stext.toCharArray();
		for (int i = 0; i < ch.length; ++i) {
			if (ch[i] == '1') {
				oneCount++;
			} else {
				result += oneCount;
			}
		}
		return result;
	}

Complexity = O(n)

public static String movefront(String stext){
int end=0;
char [] ch=stext.toCharArray();
for (int i=0;i<ch.length;++i){
if (ch[i]<='0'){
ch[end]=ch[i];
end++;
}
}

for (int j=end;j<ch.length;++j){
ch[j]='1';
}

return new String(ch,0,ch.length);
}

Can I Just Count the # of '0' and '1' ?
without using any swapping.

isn't it the bubble sort algorithm?

Step 1 : Count number of 1s

for(count=0;n>0;count++) {
          n&=(n-1);    }

Complexity worst O(n)
Step 2: add number of 1s to a new number

n = ( 1<<(count +1) - 1);

Complexity O(1) : constant time

As mentioned by NGloom, we can just count the number of 0s during the first pass - O(n) and in the second pass set those many elements from the start as 0. the rest would be set as 1. We don't even need to swap.

the most efficient way i can think of... thinking i NEED to swap is a modified bubble sort:

int swapsDone=0;
for ( int i=0; i<n-swapsDone; i ++ )
     if ( ch[i]=='1' )
           for ( int j=i; j< n-swapsDone-1; j++ ) 
           {
                 swap ( ch[j+1], ch[j] );
                  swapsDone++;
            }

// i don't think i need to explain the code

i think that the question has changed .......now we have to find min no. of swaps.

string s=00101. .....ans=1;
string s=001101.....ans=2;
string s=0011001......ans=4;

bool flag1=0,flag2=0;
for(int i=0,j=n-1;i<n,j>=0;i++,j--)//n =s.length();
{
if(s[i]=='0' && flag==1)
count1++;

if(s[j]=='1' && flag2==1)
count2++;

if(s[i]=='1')
flag=1;
if(s[j]=='0')
flag2=1;
}

ans=count1*count2;

this show that.........................

static int swapSort(String s) {
int i=0;
int count = 0;
int swapcount = 0;
char[] ch = s.toCharArray();
while(i<s.length()){
if(ch[i]== '1'){
count++;
i++;
}else{
swap(ch,i,count);
swapcount = swapcount+count;
if(count==0)
i++;
count=0;
}
}
return swapcount;
}

char[] str = "01010101001".ToCharArray();
for (int i = 0; i < str.Length; i++) {
if (str[i] == '0') {
int j = i;
while (j > 0 && str[j - 1] != '0') {
char temp = str[j];
str[j] = str[j - 1];
str[j - 1] = temp;
j--;
}
}
}
Console.WriteLine(str);

char[] str = "01010101001".ToCharArray();
for (int i = 0; i < str.Length; i++) {
if (str[i] == '0') {
int j = i;
while (j > 0 && str[j - 1] != '0') {
char temp = str[j];
str[j] = str[j - 1];
str[j - 1] = temp;
j--;
}
}
}
Console.WriteLine(str);

void Swap (char *str) {
    if (str == NULL) return;
    
    int flag = 1, i = 0;
    
    /* Flag in this while loop tells us if we did a swap in the
     * last pass. If we did, we go over the string again. If we
     * did not see the need to do a swap in the last pass,
     * then flag is zero and we are done.
     */
    while (flag == 1) {
    
        flag = 0;
        i = 0;
        
        while ( str[i + 1] ) {
                
            if (str[i] == '1' && str[i + 1] == '0') {
                str[i] = '0';
                str[i + 1] = '1';
                flag = 1;
                i = i + 2; /* Jump two characters ahead */
            }
            else i++; /* Jump one */
        }
    }
}

Count the number of '0'(z) and '1'(o) in 1 parse. In second parse fill z '0' in beginning followed by o '1' is end

I think the algorithm can be like this...
First go on parsing the string until you get '1' as soon as you reach '1' now search for '0' and count the number of places from '1' to '0' that will be the number of moves for that '1' shifting so many places. similarly count for the remaining.

To solve the problem, we can have two pointers, one beg, and another end. Then the algorithm could be something like this :
1) Keep incrementing beg until 1 is found
2) Keep decrementing end until 0 is found.
3) flip bit at beg, flip bit at end (or swap, but just flipping would work)
4) stop when beg > end

pseudocode :

for (beg = -1, end = size; beg > end;)
    while(bin_array[++beg] == '0');
    while(bin_array[--end] == '1');
    flip(bin_array[beg]);
    flip(bin_array[end]);

Linear time solution to find minimum no. of swaps required

public static int min_swaps(int a[]){
		int min_swaps = 0;
		
		//Find no.0f 1's
		int no_of_ones = 0;
		for(int lp=0;lp<a.length;lp++){
			if(a[lp]==1){
				no_of_ones++;
			}
		}
		
		int position = a.length;
		for(int lp=a.length;lp>=1;lp--){
			if(a[lp-1]==1){
				min_swaps+= (position - lp);
				position--;
			}
		}
		
		return min_swaps;
	}

Linear time solution to find minimum no. of swaps

public static int min_swaps(int a[]){
		int min_swaps = 0;
		
		//Find no.0f 1's
		int no_of_ones = 0;
		for(int lp=0;lp<a.length;lp++){
			if(a[lp]==1){
				no_of_ones++;
			}
		}
		
		int position = a.length;
		for(int lp=a.length;lp>=1;lp--){
			if(a[lp-1]==1){
				min_swaps+= (position - lp);
				position--;
			}
		}
		
		return min_swaps;
	}

int swapmin(char *ch)
{

        int n = strlen(ch);
        int i = 0, sc = 0, oc = 0;
        while(ch[i])
        {
                if(ch[i] == '1')
                        oc++;
                else if(ch[i] == '0')
                {
                        sc += oc ;
                }
                ++i;
        }
        return sc;

}

parse the string from right to left
* when doing so keep track of the number of zeros
* when you encounter a 1, add the current count of zeros to total counts

At the end of the loop, total counts will have the minimum number of swaps needed

what i think is there would be swaps amongs 1s also... which i guess we can avoid.... we dont need to perform swap among adjacent 1's

correct me if i am wrong

this is the implementation of above logic

#include<stdio.h>


int main()
{
int arr[]={0,0,0,1,0,1,1,0,1};



int countZero = 0;
int arrSize = 9,i,j,temp,k=0;
int swap=0;



for(i=(arrSize-1);i>=0;i--)
{
   if(arr[i] == 0)
   {
    countZero++;
   }else
   {
      for(j=i,k=0;k<countZero;j++,k++)
      {
          swap++; 
          temp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = temp;
      }
   }



}



for(i=0;i<arrSize;i++)
 printf("\t%d",arr[i]);



printf("\nSwaps = %d",swap);



return 0;
}

public class BitSwapping {
	
	String retStr = new String();
	public int swapCtr =0;
	
	public void arrangeBits(String inpStr){
		int pos;
		char temp,temp1;
		String str2;
		StringBuffer i_strB = new StringBuffer(inpStr);
		StringBuffer strB = new StringBuffer();
		
		//Look for 10 in the input
		//Need to swap until there are no more 10s in the input
		while (i_strB.indexOf("10") > 0){
			pos = i_strB.indexOf("10");
			temp = i_strB.charAt(pos); 
			temp1 = i_strB.charAt(pos+1); 
			
			str2 = i_strB.substring(pos+2); 
			strB = new StringBuffer(i_strB.substring(0,pos));
			strB.append(temp1); 
			strB.append(temp);
			strB.append(str2);
			i_strB = strB; 
			swapCtr++;
		}

		MyPr.pln("printing output");
		MyPr.pln("===============");
		MyPr.pln(strB.toString());
		MyPr.pln("Count of swaps "+swapCtr);
	}

	public static void main(String[] args){
		
		String str = "0001111000101011";
		BitSwapping bSwap = new BitSwapping();
		bSwap.arrangeBits(str);

	}
}

#include<stdio.h>

main()
{
int arr[8]={0,0,0,0,1,0,1,0};
//printf("enter array 8 elemenets(only 0/1):");
//scanf();
int i,j,k,zc=0,swap=0,tmp;

for(i=7;i>=0;i--)
{
if(arr[i]==0)
zc++;
else
{
for(j=i,k=0;k<zc;k++,j++)
{
swap++;
tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
}
}
}
printf("no. of swaps:%d\n",swap);
for(i=0;i<8;i++)
printf("%d",arr[i]);
}

Keep On parsing the string from left to right, and count the no of ones in a variable...
No_Of_Ones++
whenever a zero occurs
SwapNeeded+= No_Of_Ones

#include<stdio.h>


int main()
{
	char data[]="1000101110001000";
	int len=0;
	int i,j;

	for(;data[len]!='\0';len++);

	i=0;
	j=len-1;

	do
	{
		while(data[i]!='1') i++;
		while(data[j]!='0') j--;
		if(i<=j)
		{
			data[i++]='0';
			data[j--]='1';
		}
	}while(i<=j);

	printf("%s\n",data);
		
	return 0;
}

The nth 0 at distance i from the start will have to be swapped (i-n) times to reach its correct destination.

Count and distance are natural numbers(start from 1)

Run through the string and sum (n-i) for each 0.

That sum is the number of swaps required.

Dutch flag sort

#include<iostream>

using namespace std;

int main(){
string s ;
cin>>s;
int no_of_zeros = 0, no_of_swaps = 0;

for(int i=s.size()-1;i > -1; i--){
    if(s[i] == '0')
        no_of_zeros++;
    else
        no_of_swaps += no_of_zeros;
}

cout<<no_of_swaps;
return 0;
}

This works.

int a[] = {0,0,0,1,0,1,1,0,1};
    int size = sizeof(a)/sizeof(a[0]);
    int correctPosition = size-1;
    int minSwaps = 0;
    for(int i=size-1; i>=0; i--)
    {
            if(a[i] == 1)
            {
                    minSwaps += correctPosition-i;
                    correctPosition--;
            }
    }
    cout<<"MIN SWAPS = "<<minSwaps<<"\n\n";