/*
* Question:
Given an array containing sequence of bits (0 or 1), you have to sort this array
in the ascending order i.e. all 0' in first part of array followed by all 1's.
The constraints is that you can swap only the adjacent elements in the array.
Find the minimum number of swaps required to sort the given input array.
* Example: Given the array (0,0,1,0,1,0,1,1) the minimum number of swaps is 3.
*
* Note: You just need to complete the function given below for this task. The function is given a binary
string as input and returns the required answer.
*
* Solution:
* Iterate from beginning of array. keep a counter of no of 1's in path.
*
* int swaps = 0;
*
* 1) For each '1' encountered increment counter by 1
* 2) if '0' is encountered, swaps = swaps + counter
*
* Finally print swaps.
*
* Runtime: O(n).
* Spacetime: O(1).
*/
public class CountSwapsToSort {
int getNoOfSwaps(int[] arr) {
int swaps = 0;
int count = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 1)
count++;
else
swaps = swaps + count;
}
return swaps;
}
public static void main(String args[]) {
int[] arr = { 1, 1, 1, 0, 0, 0 };
System.out.println(new CountSwapsToSort().getNoOfSwaps(arr));
}
}
No comments:
Post a Comment