public class BinaryArrayMinimumSwap {
public static int minswaps(int arr[], int n)
{
int count = 0;
int numUnplacedZeros = 0;
for (int index = n - 1; index >= 0; index--)
{
if (arr[index] == 0)
numUnplacedZeros += 1;
else
count += numUnplacedZeros;
}
return count;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 0, 0, 1, 0, 1, 0, 1, 1 };
System.out.println(minswaps(arr, 8));
//Space Optimized Solution: An auxiliary space is not needed.
// We just need to start reading the list from the back and keep track of number
// of zeros we encounter.
// If we encounter a 1 the number of zeros is the number of swaps needed
// to put the 1 in correct place.
//Time Complexity: O(n)
//Auxiliary Space: O(1)
}
}
TechInsiderStory is place where you can find basic knowledge of various technology and framework. TechInsiderStory is provide free knowledge on various technology and framework.
Binary Array Minimum Adjacent Swaps Required To Sort Binary Array
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment