CODEWITHSUNDEEP
arraysalgorithm
pavle
pavle

Reputation: 113

Finding the least number of swaps to "sort" a circular array of 1s and 0s

For example, an array 10110001101110 is given and what the program needs to find is the least number of swaps for it to be all 1s next to each other. In this case it would be 2, by swapping 3 -> 14 and 4 -> 10. By circular array, I mean an array that wraps around, for example 1100001111 would be considered sorted.

The thing that I'm struggling is to find an efficient algorithm for calculating this. I first tried to transform this array into another array that consists of lenghts of strings of same numbers. For example the array given at the start would become 11232131. I noticed that this array always has an even number of elements, but I really don't know what to do with all this, or if this is even a good start to this problem.

Upvotes: 1

Views: 444

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59144

  1. Count the total number of 1s. Let m be that number
  2. Find contiguous region of length m that has the most 1s in it
  3. The number of 0s in this region is the minimum required swaps. Each swap will move one 1 into the region and one 0 to the remainder.

Upvotes: 2

Related Questions