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;
    }

    ReplyDelete