## Amazon Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**Written Test

see the total number of zeros right to each 1.here for

each 1 total number of zeros right to it are 3.hence total swaps will be 9.

For input "11000" we need only 2 swaps. But your program will print 3.

The optimal way looks to me to have two indexes: tracking zeroes from rhs (say i) and ones from lhs (j) and for as long as j<i keep swapping.

sorry got submitted by mistake.. here is the code

int swapSort(String s){

int numZeros = 0;

int count = 0;

for(int i=s.length-1; i<=0; i++ ){

if(numZeros > 0 && s.charAt(i)=='1'){

count = count + numZeros;

}

else if(s.charAt(i) == '0'){

numZeros++;

}/* end else-if*/

}/*end for*/

return count;

}/*end swapSort*/

The idea is:

- I will keep in nextZero the position of the next Zero I will have to swap

- the number of swaps for a zero is the distance between the current position of a zero and the position this zero should be.

Complexity : time - O(n) space- O(1)

```
int nextZero = 0;
int count = 0;
while(bits[k] == 0) k++;
nextZero = k;
for(int i = k; i < bits.length; i++){
if(bits[i]==0){
count += i - nextZero;
nextZero++;
}
}
return count;
```

```
int[] arr = new int[] { 0, 0, 1, 0, 1, 0, 1, 1 };
int start = 0, end = arr.length - 1, swapCount = 0;
while( start < end ) {
while( arr[ start ++ ] == 0 );
while( arr[ end-- ] == 1 );
if ( start - 1 < end + 1 ) {
arr[ start - 1 ] = 0;
arr[ end + 1 ] = 1;
swapCount++;
}
}
System.out.println( swapCount );
```

1. Count number of zeroes

2. Now - while number of zeroes before the first 1 encountered is not equal to the total number of zeroes - run a recursive Swap method.

```
int array[]={0,0,1,0,1,0,1,1};
int array2[]={1,1,0,0};
int swapCount=0;
int i=0,j=array.length-1;
while(i<j){
while(array[i]==0 && i<array.length-1){
i++;
}
while(array[j]==1 && j>0){
j--;
}
if(i<j){
swapCount++;
int temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
System.out.println("Total no of swaps : "+swapCount+" final array ");
for(int k=0;k<array.length;k++)
{
System.out.println(array[k]);
```

}

Its actually the sum of the number of 0's to the right for each 1. The pseudo code is as follows :-

- Anirban October 29, 2012