## Sunday, September 23, 2012

### [Amazon Online test] Number of swaps required

Given an array containing 0 & 1 only, You have only 1 operation i.e. you can swap theadjacent elements in the array. Find the minimum number of operationsrequired to sort the given input array.

A = (0,0,1,0,1,0,1,1)
Min Operations: 3.

Approach:
Let's start with some of the trivial test cases.
(1,0) -- Number of swaps = 1
(1,1,0) -- Number of swaps = 2
(1,1,0,0) -- Number of swaps = 4
So an important observation comes that given an array of the type
(1, 1, 1, ... n times, 0, 0, 0, .. m times)
Number of swaps = n*m (This is based on the fact that each 0 has to be pushed(swapped) back m number of time)

So iterate over the array and keep track of the 1's encountered, whenever we hit a 0 we add the result(number of swaps) with the number of 1's encountered so far(as 0 has to be swapped with each of them order to reach a configuration like (0,0,..., 1, 1, 1...))

Now the piece of code will look like

```int swapSort(int *a, int n) {
int swaps = 0;
int noOfOne = 0;
for (i =0;i<n;i++) {
if (a[i] == 1)
noOfOne++;
else
swaps += noOfOne;
}
return swaps;
}
```

#### 1 comment :

1. This Java method will count the number of operations required to sort the given array:

// 0,0,1,0,1,0,1,1
private static int noOfOperations(int[] arr) {
// This will hold the no of 1's that the current 0 will be swapped.
int ones = 0;
// Total no of swap operations performed
int noOfOps = 0;

int i = 0;
while (i < arr.length) {
if (arr[i] == 1) {
ones++;
}
if (arr[i] == 0) {
if (ones > 0) {
noOfOps += ones;
}
}
i++;
}
System.out.println("Number of operations = " + noOfOps);
return noOfOps;
}