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.
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"?
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.
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
- → 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
- → 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