# Fastest Way To "sort" Bit Sequence By Toggling Bits

Given a finite random sequence of bits, how can the minimum number of bit toggles necessary to result in a sorted sequence (i.e. any and all 0's are before any and all 1's) be determined?

Note, homogeneous sequences (e.g. `0000000`

and `1111111`

) are considered sorted by this definition.

Also, this is not technically "sorting" the sequence because elements are toggled in-place, not restricted to swapping with other elements, is there better word to describe this activity than "sorting"?

## Answer

Let Z(n) be the cost of setting the first n bits all 0.

Let X(n) be the cost of minimum cost of "sorting" the first n bits.

We have:

Z(0) = 0, X(0) = 0

if the ith bit is 0: Z(i) = Z(i-1), X(i) = min( Z(i-1), X(i-1)+1 )

if the ith bit is 1: Z(i) = Z(i-1)+1, X(i) = X(i-1)

The answer is X(n).

It's even easier in code:

```
z=0
x=0
for bit in sequence:
if bit == 0:
x = min(z,x+1)
else:
z = z+1
return x
```

## Related Questions

- → (Javascript) Take Three Integers From User to Display Sum, Average, Product, Smallest, and Largest Number
- → What is the best way in JavaScript to trim down the properties of an object?
- → How to extend Laravel's bcrypt method
- → Most efficient method to check for range of numbers within number without duplicates
- → What is the best way for me to retrieve this information in a sorted manner?
- → React Page recommends keeping logic at a high level
- → Unexpected undefined Value in JS Script
- → javascript find symmetric difference
- → Does React always check the whole tree?
- → How to use a recursive filter all single JSON data?
- → How is document.querySelector implemented?
- → Algorithm to determine correct character ['╦', '╣', '╠', '╩', '╬'] for intersections in grid
- → Optimal compression for a large base 10 number contained in a string